I've found a solution that works.
Before you do, here's the disclaimer: The Windows Registry Editor is a very powerful tool, and if used inappropriately, can cause significant damage to your operating system. It is not a bad idea to back up your system (or at least create a restore point) before editing the registry. You follow these steps at your own risk.
1. Click Start, and type 'regedit' in the search box, and press enter.
2. In the registry editor, expand the branch labeled HKEY_CLASSES_ROOT and scroll down (a long way) until you see "spotify" (Note: there may be several others, such as spotify.m4a, but we want the one that just says spotify).
3. Right click on the key on the left labeled spotify (Registry keys look like folders, but they are called keys), and left click on export. You can place the file whereever you will be able to find it later if you need it. Call it something like spotify-backup.reg.
4. After you have saved that key in the previous step, right click on the spotify key again, but this time select "Delete." On the confirmation dialog, click yes.
5. At this point, we are done with the registry editor, so you can close it.
6. Open the notepad application. Avoid using any other text editor you may have, as they may not save the file we are going to create properly. Notepad can be launched the same way regedit was launched in step 1, replacing 'regedit' with 'notepad'.
7. In the empty document, paste the below text 8. Locate the Spotify.exe file on your hard drive. The default location is C:\Users\<USERNAME>\AppData\Roaming\Spotify\Spotify.exe. If this is where it is installed on your computer, simply replace <USERNAME> with your actual username in the notepad document you have open. There are two instances of <USERNAME> to replace. If Spotify is installed someplace else, you will have to edit the path manually - remembering to use double backslashes.
9. Once you have finished editing the text, save the file to your desktop, and call it "Spotify.reg". Be sure, in the "Save As" dialog box, that you switch the drop down labeled "Save as type:" to display "All Files (*.*)" instead of the .txt that is in there by default. If you do not do this, you'll end up with a file called Spotify.reg.txt which will not work.
10. Once you have saved the file, close notepad.
11. Find the Spotify.reg file on your desktop, and double click on it. When you do this, you will get a warning message that will ask you if you want to add the information to the registry. Click Yes.
After you've followed these steps, it would probably be best to reboot the computer. After the computer comes back up, try going to a Spotify link again, and hopefully it will work.