Did you migrate or 'create' the users on the site? If you can take a look at the jos_users table for someone who can't get in, make sure that all the fields look correct. For a registered user, for instance, ensure that the following fields are setup like so:
usertype = "Registered"
block = 0
gid = 18
This is a strange issue, and really makes me think these user's were not created in a 'standard' way. Should be easy to fix them all up though, once we get to the bottom of the cause.