It could be a separate problem, but I have seen DNS servers that appears to not support RFC 2782 (SRV record) and QSpot requires a successful query for SRV _spotify-client._tcp.spotify.com. When queried, the server I saw this on always answered that the record did not exist.