that is usually a good sign your DNS is setup wrong.
make sure your dns points to your active directory server and then use the netdiag tools from Microsoft on the server to make sure your DNS is configured correctly.
you can also check the new user to see if ROAMING profile is turned on, this could cause it slow down.