Deleting all application data (when Spotify is not running), both ~/.cache/spotify and ~/.config/spotify have helped some.
1. Open Ubuntu Software Center
2. Go to menu Edit -> Software Sources
3. Go to tab "Other Software"
4. Click "Add", enter "deb http://repository.spotify.com stable non-free" in the box.
5. Enter your password in the authentication dialog that appears (note: this may not appear if you did some admin thing recently)
6. Locate the two entries containing http://repository.spotify.com that now appear in the list. Uncheck the one that ends in "(Source Code)"
7. Press "Close"
8. Enter "Spotify" in the search box in Ubuntu Software Center
9. Select "spotify-client", press "Install"
10. Pull up Unity, enter "spotify" and start the app.
11. Pin the icon in the launcher for easy access. (Right click and select "Lock to launcher").
I updated the public key and installed version 0.8.4.103 a moment ago. Looks good. All the problems I had with the previous version seems to have gone away. Thanks!