The "Linux Preview" version is first of all a bit tricky to install, and doesn't seem to be updated in a while. (Plus, it's not too smart that I - living in the Netherlands - cannot change the language of the page to English, if I choose the Netherlands under the 'Land' menu, I must read the whole page in Dutch.)
So, for some songs and albums I've got an error message saying
"There is a problem with the sound decoder. Spotify can't play music"
After checking everything I could with my sound settings - I own a Logitech Cooling pad with built-in speakers for my notebook, that caused me some difficulties to install under Ubuntu, but that's another story - I've found that the spotify-client-qt package depends on the libavcodec52 (3) and libavformat52 (4) packages which seem to be missing.
With some googling, I've found (1,2) that I'm - of course - not alone with this issue, and the missing packages are from an earlier version of Ubuntu. Not that I don't trust other people posting files to download services for patching your system (I don't, and you shouldn't either), downloaded the two mentioned packages from the 'local' ubuntu repository, and a third one: libavutil50 (5) because of dependency.
Installed them in the following order - and commands:
dpkg -i libavutil50_0.6.4-0ubuntu0.11.04.1_amd64.deb
dpkg -i libavcodec52_0.6.4-0ubuntu0.11.04.1_amd64.deb
dpkg -i libavformat52_0.6.4-0ubuntu0.11.04.1_amd64.deb
... and finally I can listen to Peter Gabriel songs in Spotify!
Note that I'm using 64bit Ubuntu, so if you use 32bit, you have to download and install the *_i386.deb packages.
Thanks for the authors of the original posts!