Regarding the inability to sync or download playlists:
I find it odd that the suppport staff were not given the appropriate info from their own developers. This is the solution that I found to work on my Toshiba laptop + Samsung tablet. I also tested it with a borrowed idevice.
1) ensure that traffic from the spotify app is allowed thru your firewall in both directions (as listed already)
2) check the uPnP settings as mentioned here: http://community.spotify.com/t5/Mobile-iOS-iPhone-iPad-iPod/Iphone-not-showing-up-in-devices-Unable-...
3) verify that the spotify app set things up properly (via uPnP) in your router - on mine this was incomplete.
On my Belkin router, there is a way to configure traffic thru the its internal firewall. It had an entry for the Spotify app on the PC, but nothing relating to other devices.
4) look up the ip addresses assigned to each device that you wish to sync to (client list from your router or under the advanced wifi settings on your device). You may also need another app on your pc to verify this next number for yourself, but I use Comodo Internet security (free) and it told me that PC spotify.app was "listening" on ports 28939 and 57621
5) create an entry in the traffic routing table in your routers' firewall, to allow traffic from your device to the spotify app on the PC, using the devices' ip and the port number that the PC app is listening on. In my case I only created one entry for the first port 28939 and the iDevice appeared in the Devices list.
When I finished the above, the PC spotify app asked me if I wanted to sync with it. Since it is not mine, I manually chose one file to sync and it appeared in the device. I then deleted the rule on my router and recreated it for the Samsung. I logged out of the PC app, quit the Samsung app, launched and signed in on the PC, and then launched the app on the Samsung. I toggled offline mode on the Samsung and it appeared in the Devices list --and I am syncing as I type.
I know there is probably a more elegant way of signing out and in on the applications that would result in jumping thru fewer hoops than I listed, but anyways - I hope this helps my fellow android users.