While specifying user name give Domain\ (for eg. MSN\userid). Hope this may help you. If you still face issue then check in Central Site Administration and Shared Services Site. There a setting is for Downloading all LDAP/AD Dump to local Server.
There must be some problem in that service/process.