I had the same problem running my Nokia Lumia 610 connected to a Windows XP computer, I tried turning off the Windows Firewall located in the Control Panel and it did not work. So I turned the firewall back on and added Zune to the Exceptions list of programs in Windows Firewall. Next I tried the other recomendation mentioned by tomekpe by turning on ...
I had experienced the same issue, and after researching on this page http://support.xbox.com/en-AU/xbox-on-other-devices/windows-phone-7/wireless-sync
you can see on section 'Compatible wireless networks' that states 'Zune players do not support the 802.11n standard.'
Since my network is 801.11n, I guess I won't be able to sync my phone...
Answer for Windows 8:
I know your problem is with Windows Vista but you question indeed is
not specific. So I want to share that in Windows 8 Zune WiFi sync does
not work right now according to an MVP on Microsoft Answer. – Vitor
Canova♦ Sep 27 '12 at 1:59