I fixed it. I read on here before that the Rio sometimes doesn't like switches. I had this on a dumb (non-managed, no spanning-tree) 10/100 Switching Hub. It doesn't sit and wait for negotiation like most managed switches, so I thought I was safe.
As a last resort today I dug out an old 10Mb hub at the office and tried that. Fired up right away. It's odd that some packets made it across but it never worked all the way. I'm just glad it works.
It's not a big deal since the only two items on that side of the bridge will be my Rio and the XBox (or other network enabled consoles and TiVo devices). But 10Mb shouldn't limit them, especially since my wireless is currently 11Mb/sec.
The odd question is, why did it work with the notebook on the switch, though? Timing issue maybe? Everything local maybe timing was fine, but across the switch and then the wireless bridge maybe it was too much or something.