imho you describe symptoms of dns problem. lack of.
but other usual suspects, in order of sgt's opinion of probability:
firewall(s)
netbios ovr tcpip is disabled
time is not sync'd betwix svr and client
no local dns server so requests going to ISP's internet dns server
Click Details button on your error message and post exactly.
long answer:
on bad client, you have netbios over tcpip enabled yes? and can ping domain controller? if no, turn off the firewall(s) for a test. manually synchronise time and time zone on workstation and server. is this Small Business Server? did you run client setup. is this Active Directory. did you setup dns.
support.microsoft.com
when i think i am dealing with name resolution problem i cheat a fix by entering ip address instead of servername when for example, joining domain (maybe it won't let you there, i can't recall)
basically, you gotta ditch the router as dhcp server and get both dns and dhcp setup on your server. and forward dns requests for address outside your lan to your ISP's dns server.
get by for now reenabling netbios over tcpip but netbios insecure so to fix long term,improve network performance and keep your dns traffic off the freakin internet, set up dns service in win2k server and manually change all clients' dns settings to refer to same.
to get internet back then you also need to setup forwarding in the dns server and possibly remove * from 'root hint' servers.
look it up at support.microsoft.com which by now is your home page, yes? (rdl)
later also set up dhcp service on the server (and then disable it on the router)
(reminder: reboot the clients or use ipconfig /release then /renew to get new ip address stuff. )
check out how to setup dns service, how to do dns forwarding, how to set client dns settings on support.microsoft.com
btw, i agree, static ip addresses are more secure and microsoft now recommends them.