The same problem happened with me when I moved the installation from root to a sub-domain. I edited all the references in the config file and DB and the same login problem. I was only able to login to the main site but not the other sites.
I am not sure but I think that there could be 2 possibilities:
1. You installed WP3 multisite in some sub-domain or folder.
2. You moved the installation to some different folder to sub-domain.
I did lot of playing around with the settings bit nothing worked out. Finally, I moved the installation back to the root and now its working fine.
If you do find the solution, please do let me know.