So I’ve made some progress. I’ve put a copy of spotify.exe in /usr/bin, and I’ve made a symbolic link from there to ~/.wine/drive_c/Program Files/Spotify/spotify.exe.
Now it all works.
I’m using an eeepc, so my home folder is on an SDHC card (formatted with ext2). Wine does not seen to be able to run spotify off of that drive. (Assuming I’m right in thinking firfox downloads to /tmp?)