I was convinced at some point along the way that it had to be a network issue because perhaps I didn't have Multicast and Universal Plug and Play (uPnP) working right. I am running a Cisco Pix 501 for my Firewall and Router and a Netgear GS724T for my switch. Those are both non-home devices and maybe they were part of the problem.
After exhausting efforts there I decided to take another look at my computer itself. I am running a licensed business edition of AVG because I am a big fan and most things online point to the problem being a firewall configuration for it. I am however NOT running their firewall because I am running my network behind the strict pix configuration. This means I am running the stock Microsoft Windows Firewall that comes built into Windows. I had been trying to get the communication between the Xbox and the computer to work with it both enabled and disabled with no luck and I kept getting the same error of "Cannot Configure Extender".
I decided to enable the Windows Firewall again and check the program settings for enabled apps which revealed that the "Media Center Extenders" and "Windows Media Player Network Sharing Service" was not checked. Checking them and clicking "OK" made communication work instantly and the problem was resolved.
I followed all the instructions I could find and even went to http://www.xbox.com/pcsetup like the Xbox screen says to do but this bit of instructions wasn't mentioned so I am posting it for others in case they are beating their heads in on the same issue.
