I was in touch with somebody from Spotify today, trying to help me out, despite the fact that the eDGe is not supported by them. He gave me access to a test account to check whether the problem was due to some personal stuff for my account (to many playlists for instance), but without success so far. I've offered them to be willing to test things etc. if they're interested. If anything interesting happens, I will post it here.

I'm from the Netherlands, having a Premium account on Spotify, so access should not be an issue with respect to location, etc.