I found a work around on the
Apple Support Discussions section.
Paul Wieland (of Apple Discussiuons) said:
There is a bug (do a search for smart playlist in this forum) with smart playlists not displaying the correct songs on the iPhone.
I just tried something that seems to have worked...
I have a playlist in iTunes called "Recently Added" which I want to keep synced with my iPhone.
I created a new smart playlist called "Recently Added (iPhone)". The playlist has one rule: "Playlist is Recently Added" with live updating checked.
I now sync this second playlist with the iPhone and all the correct songs show up in it.
Hope that will help people who are having this issue.
This seems to be working for me, so I will continue for the time being.