Just through this out there because I know it is the same on BlackBerry, but you might need to manually set your carrior APN to get it to work. My post about doing this on BlackBerry is here if it is any help.
I have almost exactly the same problem on my Lumia 820 : ( Login Failed - Unknown error (112) ) and was happy to find this thread. Is this a known bug to Spotify to be fixed, when the WP8 gets out of its Beta-Phase?
Manually setting my carrior APN to get it to work is not the solution I wanna have even after Beta, when I pay 10€ a month to use a service.
i have uploaded and uninstalled on my mob(samsung experia) still no joy at accessing spotify premium on there aaaaaaaaaaaaaaaaaaaaaaaaaaAAAAAGGHHH! I really need it to work...any ideas? it IS a spotify problem as any other apps i use do work fine... SPOTIFY, or anybody please help . I feel a tenner a month for this feature would be fine IF IT WORKED...in hope of a solution, truthshome