I honestly think I have enough anecdotes to officially be "against" them now. Here's the process I had to follow to get my 360 to see my PC, even though everyone involved was getting to the Internet just fine through the router:
Hi guys.
I had the same problem and just found a solution that finally allowed my PC to see my XBox. I thought I'd post it here so the rest of you can finally overcome this issue. All credit goes to Alex (OldSchoolGamer) on the www.technologyquestions.com forums for providing this answer:
*****
Ok this is not an issue with a firewall, it took me 3 calls and about 12
transfers to get an answer. For phone help dial 1800-4MY-XBOX then get to
live console help and ask to speak to the hardware department. Describe
issue, most likely will get transferred a couple times till you end up back
at the hardware depart, let them know its a pc failed message. They can walk
you through it.
Its basically a DRM (data rights management) problem. Steps to fix are as
followed:
Click start, go to run
type services.msc
go to Windows Media Player Network Sharing Service
double click it and hit stop
then you will need to be able to see all hidden files and folders:
Open my computer window, and click on the tools tab at the top and select
folder options, and click the view tab
Scroll down make sure show hidden files and folders is shown
then scroll further down and uncheck hide protected operating system
files(recommended)
then you must delete the DRM files in Windows Media center folder:
Click on My Computer, choose your harddrive (usually C:) click on documents
and settings folder, then All Users Folder, and you should see DRM folder
Double click DRM folder
Control and a to select all the files, then shift delete (to skip sending to
the recycle bin), then hit yes, now close this window
Go back to run, type services.msc and highlight Windows Media Player Network
Sharing Services and right click and select start, this should fix the
problem varify you are still sharing the connection via windows media player,
library tab, share media option, and that it still sees your xbox,
restart xbox: go to media tab and select music, choose computer it should
now search and (yes finally) find your computer
Have a nice day