User Permissions Messed Up following a Backup -> Restore Operation
I see you already found a solution to your problem, one thing I noticed in your original question was that you still had access to the old server.  

The following question on SO had a similar problem and includes links to a Microsoft article with a script to generate the user permissions.

https://stackoverflow.com/questions/461385/restoring-a-backup-to-a-different-server-user-permissions

(Resource listed for that question http://support.microsoft.com/kb/918992)

It sounds like changing the server setting from Windows authentication to Mixed mode authentication fixed your problem, but just in case it didn't completely resolve the problem I thought this might be useful.