I'm having the same issues as last night.
It seems that ever since I upgraded to 1.80, having the PS3 on wreaks total havoc on my entire network. PSN drops in and out. My PC's internet drops in and out (and my IMs get signed out all the time), and though I have WMP11 properly set up for sharing (can access all of my library via the X360), when I try via the PS3, I get a connectivity error and an eventual "Not titles to display" error.
If I do a network test on my PS3, I get NAT Type 3 and UPnP not available, despite the fact that pre-1.80, I had no NAT or UPnP issues. I dunno wtf 1.80 did, but it effin' sucks to be my network now.
PS, it's a premium PS3 that's otherwise hardwired to my network via a reliable WRT54g v5 Linksys wireless router. I stopped trusting the wifi months ago.
Edit - I followed the XP steps listed by the OP and verified that UPnP is started and set to automatic. And of course, I enabled sharing with the PS3 (unknown device) last night. Those settings match my X360's settings perfectly.
Edit 2 - Followed the advice of a buddy of mine with similar issues, and disabling the media server auto-connect restores my network to usual UPnP and NAT Type functionality... but of course kills the streaming from my PS3. I realize I still have my X360 for this, as a viable option, but now I'm irked that I can't get it to work. I can only imagine that if it works right on my X360, then there's absolutely nothing wrong with my network settings, and it's an issue with the PS3's software?