I am seeing the same problem, but actually the tracks have been downloaded and are playable in offline mode. The next screen capture shows that Spotify is offline, and just to be sure I also disabled both Wi-Fi and 3G. Still, despite the missing green arrow icon, the 4th item "Milonga Del Mar" is actually playing just fine! Other tracks without an icon are fine too.

Of course, one might want to be VERY sure one is not downloading when not explicitely using offline mode, so it's still quite annoying that the icon is not shown. If I go into online mode and enable 3G, then for truly not downloaded tracks (of non-downloaded playlists) I see much more traffic than for the above tracks. For the latter I do see some traffic for a very short time, probably the app phoning home to Spotify that I started a new track?
And, who knows, maybe other missing icons in downloaded playlists do really indicate the track is not downloaded. (For the OP, JohnnyDubs, things certainly resulted in unexpected downloads, so my case is different!)
Also, using the inline menu in the playlists screen to delete the download and then enabling it again, does not delete nor download anything at all. (Some caching? But then how to free space on the SD card?) However, deleting using that same inline menu and then downloading using the big green "Download Playlist" button in the playlist itself, does initiate a new download. Still then, the progress bar in the app stays at zero %, but the Android notification area does show the actual progress. But then, when all done, things are exactly the same, whith the same icons missing!
Messy.
This might only apply to items I earlier downloaded (or at least: tried to sync) to another 16 GB SD card, which broke during a Spotify sync... But I don't have a lot of playlists so can't be sure.
I guess I'm going to create a lot of playlists and leave Spotify in offline mode after that.
(HTC Wildfire S, latest Spotify, 32 GB SD, Android 2.3.5)