Hey Matthew, I got my app approved after submitting an appeal to Apple. I would recommend looking at laszloxgergely's comment in this thread; it outlined the approach I used for getting approval from Apple. I still am hoping to receive approval from Spotify to become a commercial application so if anyone has any advice on how to accomplish this, I would really appreciate it!
I am in exactly the same boat at the moment. I've sent a message to Apple yesterday quoting the Spotify developer terms and restrictions. I'll let you guys know how that went. If that doesn't succeed we'll have to figure out how to reach spotify for written consent somehow.