I'm having the same exact problem with my Samsung Exhibit...I've been using spotify with this phone for a year with no problems. Now my device will not not show up on my PC (Windows 7).... PC and phone are on the same wifi, both logged in with facebook (Also tried logging both in with User name), checked firewall settings, phone is online. I got nothing. If I add a playist it will show up on my phone but as soon as I go "offline" it's are greyed out. Even if I download the playlist via the app it doesn't work offline.. I live in NYC so I listen on my phone "offline" 90% of the time.
Mine has finally been recognized! Honestly, I have absolutely no idea of which solution was the most adapted to my situation but all I know is that I have done everything people said previously. I was done with all the unistalling/rebooting/unblocking and-so-on process, when I ceased any other attempt. Then this little notification with the name of my phone finally showed up.
I really wonder if you'll find my answer helpful but ... good luck!
I recently had a similar issue when I switched from my HTC Desire to a Nexus 4. The Nexus wasn't recognized by Spotify until I physically conencted it to the PC with a USB cable (the HTC had been fine). I synced a playlist, disconnected the USB and found that the phone could then be discovered over wifi no problem.
When I first connected the phone to the PC, Windows obviously installed relevant device drivers - I wonder if this what is necessary for the wifi to function? Doesn't seem likely, but hey.
I synced my local files from my laptop to my phone the other day, then I cleared the cache (doh!) so I lost the synced files.
I took my laptop into my office and connected both my phone and laptop to the same network but couldn't get the two to sync up. Once I left the office I turned on my wifi hotspot on my phone and boom, my laptopcould see my phone.
Lesson is... some network setups will not allow spotify to talk to your phone and vice versa so check your connection. I'm guessing the internet at work is super secure, for instance in windows 7 whilst connected to my work internet I cannot see my office computer under the network tab despite being on the same network. Something to look out for, no idea how to fix the solution, I'm just happy I got mine to work!