'Recently Added' and 'Recently Played' are not syncing properly

[stephenc92]

This is the correct recently played playlist on my iTunes:
http://img.skitch.com/20091019-qgys2c1yw75rfjad294xeki6n2.jpg

This is how it looks on my iPhone:

http://img.skitch.com/20091019-sur29jhn27q5qt4fihi2b6sey.jpg

Anyone know how to fix this?

[nmatese]

This is also happening for me with recently added and recently played. It seems its either the new itunes or 3.12 its driving me nuts.