Spotify requires a constant connection.It could be an issue with differing signal strength as you move around, not being enough to keep up with what is streaming. Is your phone ok outside browsing webpages? If so, good, but for a better comparison,try lowering the quality of the music if possible on spotify to see if that makes a difference. If it works then it could just be a signal not of a consistent strength. Does it cut out outside on other good quality radio websites such as last fm, radiofeeds, or (a good test if you have enough net allowance) youtube 480p - 720p medium to high quality videos with the headphones outside?If not, then it may be a Spotify problem. I believe spotify encrypts all loaded music data, so the play bar continuing instead of pausing may not indicate anything relating to the program or your signal.
As cutting out can be related to lack of ram memory or other programs hogging your internet bandwidth, make sure no other apps set to automatically run or update in the background when you switch to your regular internet, not on wifi. Many phone apps immediately update when they find an internet signal, which can be a pain and take a while to finish, depending on the amount of apps you have installed. Game apps can take a long time in updating once connected to the net.
Make sure no programs that you don't need running are on when you use spotify or go online. Switch your phone off, turn on, switch to your non-wifi net, and test. Do not run any other apps.
To check your internet settings (on O2 in the UK as an example), I think you text ACTIVE to 2020, save and reboot. That would give you the set up for the internet with O2. Most major phone companies will have something similar for a contract or not if you check their forums. Your phone is likely to have the correct settings installed already, but it might be worth a try. Also post in the Nokia forums, you're likely to find someone with a solution if it's a headphone or phone internet issue. I am googling however and finding the same Spotify problem with many phones right up to the iphone, and it turns up to often be just a common signal or bandwidth problem.
To make sure there is no conflict, as a last resort you could turn unnecessary modes related to the internet or not off, or anything else to test, bluetooth, screen dimming, screensavers, etc. If my phone was unlocked and only Spotify had the issue, then I would end up trying another sim or memory card, making sure all apps, files and address book were backed up first, but I don't think you have to go that far.