Ipad 2, no apps running, start Spotify, search for a band, after 20 seconds nothing. Touch the "What's new" button and then the "Search" button and suddenly the search results appear.
Re-test the above completely with different pause durations between switching modes, same behaviour every time.
To verify Spotify and wifi I killed the app on the iPad and then ran on the iPhone 4S, works straight away, every time, as does the iMac.
Ipad app pretty much unusable. Going to try playback again to see if any patterns emerge.