(Cant beleive Spotify doesnt have this feature)
Donwload the latest Spotify APK
(This fix applies for the ver .08 as the changed values are different dep. on version.)
Download APKEdit (Thx "whiskeybro", hope this is ok with you)
Open SpotifyAndroid.APK in the editor, go to the "Content" tab and at the bottom there are folders and files, Rightclick on "AndroidManifest" and choose "Edit"
Change the following value: "nosensor" to "sensor". All of them
Delete the string "a:configChanges="keyboardHidden|orientation"" . There is only one.
Save the file and close notepad, Click "Apply" in APKEdit.
(APKEdit may hang here, let it work and it should have created a new APK, saving the old as .backup)
Install the new APK
Ive noticed a bug during the initial login and changing orientation.
Do it in Portrait mode and let it load your data before changing orientation.
Otherwise it works fine in landscape (lists, play, search, artist info etz)
Latest version with FIX (version 0.4.9.181)
Tested only on Nexus S, hope this works on other phones, it should