In response to question 1, how slow are we talking about here? Like seconds or minutes?
You should verify that the client PC's are pointing to the domain controller's DNS server (or another DNS server in the domain). I would assume you are using DHCP to serve out the addresses, but you may have static addresses which means changing manually on each workstation. I have seen this many times, especially with WinXP clients.
To continue resolving external addresses you will have to set up a forwarder for your DNS server, pointing to your ISP's DNS server.
Hope this helps. If these settings are correct, then post back with more details. Also, regarding question two: Can you post the exact "phonebook" error message?