Interesting! Doesn't sound like you have the orphaned user problem either.

Another thing to check would be the user has connect permission on the database - take a look in sys.database_permissions