How to make Spotify links work in GNOME.

Add a protocol handler for Spotify

gconftool-2 -t string -s /desktop/gnome/url-handlers/spotify/command "<path to spotify wrapper script> %s"
gconftool-2 -s /desktop/gnome/url-handlers/spotify/needs_terminal false -t bool
gconftool-2 -s /desktop/gnome/url-handlers/spotify/enabled true -t bool

Spotify wrapper script

#!/bin/sh
# Opens a Spotify URI passed as arg, or starts Spotify if executed without args

SPOTIFY_PATH="$HOME/.wine/drive_c/Program Files/Spotify/spotify.exe"
if [ "$#" -eq 1 ]; then
    wine "$SPOTIFY_PATH" /uri "$1"
else
    wine "$SPOTIFY_PATH"
fi