Hey here in Finland I use a slow and cheap 3G for my Lumia 800.
Speed is pretty slow - just 0.5M -> 80 kb/sec - but this is enough for my use. And Spotify 320/160 kbps works well!
But price is cheap, only 4,90 € per month and Unlimited data... If you listen a lot music with 3G Unlimited data plan must have.
If you have any further questions about 3G and Spotify, just ask...
And Spotify Mobile 160 kbps mode works well in EDGE speed too! Max. 200 kbps in EDGE, I believe.
And at home i have 3G connection too, 13,90 € per month, max. 15M speed and Unlimited data. But in next year I update my Lumia's speed and start using my Lumia 800 new feature Tethering. And then I stop my 3G plan with USB modem. I can keep then my modem after 24 months, now I used this modem about 13 months, so soon it's can be stopped. 11 months to wait. 🙂
The Nokia Lumia 800 Spotify app seems to be Beta. For example yesterday I go to bus with my awesome Bluetooth headphones, but... Spotify can't play any track with those... no new news... This makes it at random. But so boring without music, and did not have time to fight before the bus.