It seems that this is only affects to date related smart playlists (ex: Songs added in the last 6 months, etc.).
There is a discussion going on over on Apple Discussions. There is a workaround that someone posted over there.
Here is the link:
Apple - Support - Discussions - 8GB iPod Nano not syncing playlists ...
-----------------------
The workaround that Paul Walker on Apple Discussions posted is:
Further to my earlier update I've had a minor success...managed to get a Recently Added playlist to work...of sorts.
Anything to do with date orders as in "Match the following rule Date added is in last 30 days" the iPod nano doesn't seem to understand, or rewrites the playlist as it's added to the iPod.
So I tried unchecking the "Match the following rule" and just left the Recently Added playlist as "Limit to 100 items selected by most recently added" and it's worked...I have a playlist of 100 tracks that are in the order of most added on the iPod.
--------------------------------
This fix works for me and fits my needs for many of my playlists. I am still patiently waiting on Apple to fix this, because I rely heavily on my smart playlists that are date related. My nano is only a 2gb.
Hope this helps.