I just started having this problem. It started just a min ago. I'm running Xubuntu 12.04 64-bit. I went to Synaptic and marked the client for reinstall. Didn't work. Marked it for uninstallation, uninstalled it, then marked it for reinstallation. Still doesn't work.
Open the terminal and type:
Use ctrl+z to divorce the Spotify session from the terminal. If this worked the problem is that the Spotify client needed files that were put in a folder owned by the root user. For some reason or another it lost permission to get those files. Same thing happened to me.