I have experienced what you're speaking of Rad, but have not spent any time trying to overcome it.

Basically in XP/2003 if the machine is NOT a member of the Domain yet, it won't allow you to add accounts or groups from the Domain.

I'm not sure if it is some policy setting that can be altered on the local box or what. But as you say, did not appear to be an issue on Windows 2000, sort of. If you had less then SP2 or SP3 then I think it too didn't work.