Could you pop in an email about this at all? We're looking into something similar and your information might prove useful...
I did a bit of a fiddling around with the OS and Spotify client. I did it again. I factory reset the device + formatted USB storage and the SD Card - I installed Spotify as the first app from Play Store, I set the device to use Wifi -> Opened the Spotify Client -> Logged in with Spotify Credentials -> Majority of the playlists loaded fast and few playlists / folders took few minutes to load.
I'm trying to see if I can replicate this with my Sensation. Both phones now run the 4.0x Android and newest Spotify Client.