If you have set your store as private store in your account settings ("Settings"->"Advanced"-"Private Store"), this means new customers aren't allowed to login until their accounts have been approved.



Please go to Sales-> Customers, check the boxes in front of the new customers and click 'Approve' to approve their accounts.