I have noticed that my latest playlists are not visible on my HTC Desire S when in offline mode. If I create a new playlist and mark it as available offline it will disappear when I go offline. When I go online again, the playlist reappears. It does the same for playlists created on the phone and on my Windows Desktop.
I have deleted the cache and reinstalled to no avail.