When you attempt to add users, what kind of message are you getting? For example, when you go to your site collection People and Groups and attempt to add a user, can you use the address book to find ANY users? Or is it finding users successfully, but from the old domain? Is the old domain still accessbile?
The way SharePoint works is that AD users are "imported" when you add them to a site collection. These SharePoint objects are bound to the AD users based on their SID, so be aware that even if your new domain users have the same usernames as their old domain accounts, SharePoint will not consider them to be the same user. IOW if OldDomain\jsmith owned a document when the SharePoint site was in the old domain, then NewDomain\jsmith will not automatically be granted access to it. It sounds like your problem is running deeper than this but it's something to be aware of.
What version of SharePoint are you using? MOSS or WSS? They are slightly different in how they access domain resources. With WSS, user profiles are imported once, when the user is first added to a site collection.
With MOSS, there is a daily scheduled import, which continually scans Active Directory for users and imports them and updates their details. If this Profile Import is still pointed at the old domain, it may be the cause of your problems.
Check to make sure that your Content Access account has permissions to the domain.
I guess it's worth asking, at this point, what kind of errors you are seeing on the SharePoint server. If you are having security issues with the new domain, then the Application event log and the logs under the 12 Hive (C:\Program Files\Common Files\Microsoft Shared\Web Service Extensions\12\Logs) should be full of useful information. Feel free to paste any errors into this thread.
