You have to sync twice to get the playlists on the iPod fully updated. Apparently, though the first sync sends your iPod's playcounts to the computer, it doesn't send the updated playlists back out to the device right away.

I've gotten around this by writing an Applescript that waits until the iPod unmounts from the desktop and then tells iTunes to sync it again. (It's automatically triggered by Do Something When when my iPod mounts the first time.)

In addition, my script also tells iCal to update my subscribed calendars (from gCal) in between syncs so the second time it gets the updated events. I don't have an iPhone so I can't edit calendar entries from the device, so a simple one-way subscription works for me. If the Touch had come with editable calendars I would have already bought one, and I'd probably have used Plaxo to sync with gCal...