Not uncommon – If you look at the security entries for SQL server you will find your user, but when you look in the database itself the user won’t have access granted.
In QueryAnalyser you can access the stored procedure dbo.sp_change_users_login (found in the master database) and apply it against your user and the database that is denying access.
[change to reflect your database name]
sp_change-users-login, ‘Auto_Fix’, ‘database’
should update the user list and restore access.
Did you do both adds from the same workstation and same login. This problem usually happens when one of the adds was done without SA access.