A – what OS was the old server? NT4, Windows 2000, 2003 on old box?
B – What client? 95/98, ME. 2000, XP, some variant of Linux/BSD/Solaris?
C – What network? Are there any firewalls? Did DNS update correctly? Is it all the clients?
D – Did you have a HOSTS/LMHOSTS file(s) setup? Were you using WINS and did you stop when you switched to the new server?
Hopefully one of these questions will give you the answer, if not, the answers to all of them will make it easier for us to help you. Good Luck.