When new users are created they should automatically be added to the "Authenticated Users" role. I would check if your users are in that role or not. If you imported users directly into the database then they would not have that role unless you add them to it, but if they register using site registration they should already be in the role.
Hope that helps,
Joe