I got a Nokia Lumia 800 with Windows Phone 7.5. I can use the celluar network on all other apps, but spotify is still shown as offline. This is kind of a huge bug that should be fixed quickly..
Wifi seems to work.
I've changed all different setting for the celluar network but can't get spotify to go online with it.
Hope for a fix soon!!!!