So, I can connect to Xbox live through my 360, I can download game demos and arcade trials, so obviously I'm online and thus connected to the network, using a D-link wireless/ethernet bridge that the xbox accepts and seems to treat as if it was the official wireless adapter (this one's model number, though it looks like that one). Yet when I try to use the windows media center connect thingy it says:
Your console isn't connected to your network. make sure your console is connected to your home network using an Ethernet cable or wireless connection.
I'd prefer not to pull a cable right through the room, and I don't have one handy anyway (strangely enough, I seem to have just about every other imaginable computer accessory and spare part), but I'm thinking that if online works the LAN functions should as well, no?

Your media server have a software firewall on it?
Also just to make sure, the Media Server is working properly right? If you're using the Windows Media Server, try installing "PS3 Media Server" (Yes it works for the xbox as well) and make sure that it's not just the Media Server Software.

The Windows 7 PC has no firewall other than the Windows built-in one. And this is for the initial media center setup, if it matters, they have never been connected before.

Ok, two things I would check... what's the IP and Subnet that the XBox has and the Win7 box. Make sure they're on the same subnet.
2nd, install PS3 Media Server. http://ps3mediaserver.blogspot.com/
Just to make sure that it's not a connectivity issue (You can remove the PS3 MS afterward, if you really don't want to use it.)

Both boxes are set to DHCP:
PC is 192.168.5.153
Xbox is 192.168.5.154
PS3MS says "PS3 Has not been found". Should this thing even work with an Xbox? I don't have a PS3.

It should work with an xbox (it does with mine).
Ok, you mentioned that it's just the windows built in firewall, have you tried turning that off yet? (If it works we can turn it back on and just open the ports that are needed)

My googlefu came up with this site:
[url=]http://social.answers.microsoft.com/Forums/en-US/vistanetworking/thread/4eb46abf-df54-4252-b7e8-a1544de1d81a[/url]
Is that of any help?

(originally an edit to the previous post)
Also, doing any of the connectivity tests that the xbox provides fails miserably... except I can log in and download demos as if everything was smooth as silk.

is upunp on?

Not much actually, the plan is to not pull stumble-prone cables through the room. Besides, both network interfaces in the computer are already used - one directly to the 'net, the other to the internal/private network behind the router (which the printer, xbox, and various other computers also connect to).

Any change with the windows firewall being turned completely off?

I haven't changed any default setting for that... hmm, lemme check the services.
...
...
"UPnP Device Host" is started, anything else?

This brings up an interesting question... why is the PC connected directly to your internet, rather than sitting fully behind the router?

Nope.
The Xbox "Test Connection" fails between the xbox and NAT/router, not between the NAT and computer.
This is leading me to think that I'll have to shell out for an official Xbox wireless adapter. Those things are expensive!