Sorry for being such a cynic, but I see two possible answers coming from Spotify support here...
If the user is using the current Android app the suggestion will be to upgrade to the preview app and see if the search works there.
If the user is already using the preview app the answer will be something along the lines of... This is only a preview app and our developers are still working on it. Hopefully the search will work better when the new Android app is finally released.
On both. Although on the play store version there is an Orion to use google voice. Which works to a point. However on the preview app there is no google voice option. Really frustrating as I have to search for music on lap top then add to play list that way.
Dazzam - Just to clarify, are you logging in with the username 'dazzam' here? It looks like you have two accounts, a free account and a Premium account. If you use the username 'dazzam', you should be able to login and search. If you're accessing the free account, this won't be possible.
Steve - No need to be a cynic. The preview app does appear to sort a lot of issues with ICS, as it's compatible. This is why we suggest it. It is a preview app, yes, but this doesn't mean we won't help troubleshoot.
If you feel as if you can offer any support at all, as an Android aficionado, please do so.
Ok, I have done all the above and still no joy. This is the same over WiFi or 3g. I now don't have the googlevoice option either. I am on HTC sensation android 4.0.3. When going into search it brings nothing back not even songs in my playlists. I am using it online. Darren