I noticed since a couple of days ago, the smart playlist "Recently Added" started to behave irratically my iPhone 3G. I am running iPhone 3.1 and iTunes 9.0.2 so I can't be sure to which update did this problem start. Basically, my recently added playlist should have my newly added songs displayed from the latest to the earlist; while it does so on my laptop, iPhone would be all shuffled up thus nearly defeating the this smart playlist.
A quick research on Google showed several postings where people have identified the bug as the Live Update checkbox in the said smart playlist. Simply by unchecking this box, problem will solve; well, sort of. Once you uncheck this Live Updating box, you've pretty much rendered this "smart" playlist to "stupid" since by definition this live updating feature will keep the playlist updated. While some do say that the list continues to be updated, I am just hoping Apple software engineers can quickly get around to fixing it so things are back to usual.
Lately, I noticed my iPhone no longer even recognize that Recently Added smart playlist (and I am not alone)... very irritating and bad mobile experience!