The short answer is, at least for the user you list: this is how it is supposed to work with the new user privilege model in 2.4+
The userAdminAnyDatabase role means that the user you have now created will be able to grant access (for itself, or any other users) to any other database, hence the designation in the docs as a "super user". However, that does not automatically grant that admin user read/write permission on all those databases (though it can bestow them upon themselves). Hence that user can't authenticate against anything other than the admin DB, but by being able to do so, it can grant the relevant permissions elsewhere.
I think what you might be looking for is the readWriteAnyDatabase role, though I would recommend using that particular role sparingly (if at all) and instead grant access as needed, for greater security.
I can't really speak to the user permissions prior to removal, because they have not been listed, just the role of the new user.