I keep seeing issues with offline play and I'm still sticking with you Spotify, but you're really starting to get on my nerves.
Anytime I start up the app fresh while I'm offline (underground, subway, or even just airplane mode), I either don't see anything under "Your Music" => "Albums" or I'll tap on an album that I know is offline and I'll see the message: "You haven't saved anything from <Album Name>. Save this album to keep it in Your Library."
You can see in the attached image, that the album is both saved to my library AND saved for offline play.
Seriously guys...I commute for almost an hour each way, mostly offline...let me listen to the music I pay for.
UPDATE: Contacted CS through twitter, seemed to be an issue with my offline cache. Haven't had issues since.