What'll you'll want to do, is open the database in question using an adimistrator password.
Then you should be able to go to File > Access Privileges > Passwords.
Once there, select the password whos settings you want to change, and make sure that Browse records is selected.

If this doesn't help, try checkin to see if any fields on the layout is marked to not allow data entry. If so, you'll have to change this. If you can't enter data into a field, you won't be able to use it for searches either.