When you go under Network and Sharing Center, does your network show up as Home, Work or Public? You want to make sure it is set to Work (Home would work too, but stick to work). You could shutoff the firewall completely, if you haven't already.
Also, check to make sure none of the items under your Network Adapter settings are unchecked. You need to have Client for Microsoft Networks enabled, which is by default, but worth asking.
I am sure there is something simple missing, and I think you are right to be looking at DNS, since it is so tightly integrated into Active Directory. When you re-installed DNS on the Windows 2008 server, you did make sure it was AD Integrated, correct? NSLOOKUP should work.. when you first go into it, just type:
server {ip address of DNS server} and hit enter
then do your machine name lookup, or lookup of the domain controller... etc.
Other than that, good luck!!