I read this forum post a couple of weeks ago and agreed that this was hole in the Android platform, so I wrote an app. My app "iSyncr" (in the Android Market) will allow you to sync iTunes (Windows Only) playlists with your Android phone. It also runs a service on your phone that keeps track of playcounts, skip counts, and last played time (that is it for now, I'll add last skipped time and other stuff later). So you can effective sync a smart playlist with your Android phone, which is all I really wanted to do to begin with. Note that if you use this, you won't want to sync last.fm back to iTunes, because it will double your playcounts.
My app is still new and I'm updating it often, so feedback, bugs reports and features are welcome.
Here is a link to the FAQ and Tutorial for the app
JRT Studio: iSyncr Tutorial
JRT Studio: iSyncr FAQ