Since the update to iTunes 9, my smart playlists have been scrambled and not syncing in the order I tell it to. I called Apple support and they couldn't offer a solution. However, they were very nice and informed me it wasn't the iPhone firmware, but it was an iTunes 9 issue. I had hoped iTunes 9.01 would fix the problem, but alas, it didn't.
I needed to come up with a work around, since I use two very important smart playlists -- recently added & 25podcasts. Essentially I have a playlist that shows the recently added stuff, from newest to oldest. I also have a 25 podcasts lists, that sort, you guessed it, from newest to oldest. The syncing problem was shuffling them all around and sometimes not even putting the correct content in the list.
Here is a temporary work around:
1. Open iTunes 9
2. Edit your smart playlist (control-click or right click on it).
3. Enable live updating so that it will show the most recent content. Click 'Ok'. Repeat process for each that needs editing.
4. Now Disable it and click 'OK'.
5. Sync your iPod/iPhone.
Your edited playlist should now be synced just like they look in iTunes.
You will need to repeat this process each time, until Apple fixes the iTunes bug. Hopefully iTunes 9.02 will work as it should.