Sorry, I'm actually stumped. Removing the app and reinstalling on my iPhone 4 fixed the problem for a little while, but it didn't last. The problem returned after a little while. I've essentially given up on it.
Thanks for the feedback. I had the same issue. When I first updated Spotify to the version that allowed following, it worked for a while, then it stopped. Now, no matter how many times I delete and reinstall, following doesn't work any more.
At least I know I'm not the only one with this problem. It's really frustrating. I hate having a gazillion playlists, when basicallyy I'm simply intersted in an artists entire discography.