After hours of confusion, tyring to figure out why my new virtual machine with Windows 2003 Server would not access the Internet (DNS did not seem to work) using the Virtual PC's built in NAT, I did a little searching and quickly found:
http://blogs.msdn.com/virtual_pc_guy/archive/2005/01/06/347965.aspxWow! Simple and easy fix! It just needed to have the DNS server set to 192.168.131.254 and everything was super-duper fine. Wish I would have started that search before trying everything I could think of, including digging through my router :)