I had this and it was an absoloute c**cking nightmare to sort out - i too tried all of the things you say and it wouldnt work, plus I had the same symptoms - xbox 360 seen in media player and allowed access - xbox360 not seeing PC.
The above poster is correct in that it works straight off if you have media centre - the xbox functions as a media centre extender, however you can use it with non-media centre pc's by browing through the shares....
Anyways to cut a long story short, it wont work with SP3 installed under XP - for some reason this creates some havoc with the media extender in media player 11, if you downgrade to media player 10, apparently that fixes the problem, if you uninstall sp3 install the xbox meda server software from microsoft and then reinstall sp3 (it wont install with sp3 installed) then that works.
What worked for me - very frustratingly and inexplicably after 2 days of constant irritation ws booting up one of my old PC's (that only had SP2) and installing the microsoft windows media connect software (
http://files.filefront.com/Windows+Media+Connect+20+English/;5479102;/fileinfo.html ) which my xbox found straight away, for some reason this also allowed it to see me main PC ????? No I dont understand it either.... and more bizaarely the xbox has continued to work flawlessly despite the computer that fixed the problem being now dissasembled in the loft....
Standard microsoft dysfunctionality if you ask me, they seem to have a habit of doing stuff like this especially when it comes to network connectivity, I have four PC's and the remote desktop connection works one-way only between three of them, not at all between two in particular and perfectly between two of the combinations, all at the same time as the network shares and print shares all work flawlessly, two years down the line and i cant figure it out.
Facebook
Twitter
Instagram