Hey All,

I too was having this issue. I was about to break my phone in two and cancel my subscription. I REALLY hate that I have to be tech genius to work simple things on my phone. And im not implying that I am a tech genius, just get so annoyed with things I will try to find a solution before I go insane. 

Solution:

(1) Uninstall spotify app from your phone

(2) Make sure all saved data is deleted from phone - applications data

(3) Restart Phone

(4) Go to http://m.spotify.com/us/

(5) Click on manually download to phone. 

(6) Once download is complete, click and install

(7) Restart phone again

At this point the app should open. Log in and get on. Once this happens, you should be able to get in the app store and update. Let me know if this works for others.