For a Most Recently Added Playlist for music on iPhone 4, iOS 5.0, iTunes 10.5 (141), Here's what worked for me after lots of experimenting:
To Create a "100 Newest" playlist:
1. In iTunes, delete any previous 'X Newest" playlists if they've not been syncing correctly since iOS 5 update, especially if they have referenced other playlists. In my experience if these playlists are not syncing in the correct order, there is nothing you can do to make them sync in the correct order - cut your losses and delete.
2. In iTunes under 'Library' in the sidebar, select 'Music"
3. From the 'File' menu select 'New Smart Playlist'
4. In the pop up box that appears, check 'Match the following rule:'
5. In the next line, in the pop-up menus, select the following: 'Media Kind', 'is', 'Music'
6. Check the "Limit to" checkbox and enter the '100' in the box, and then select the follwing option in succeeding popup lists: 'items', selected by 'most recently added'
7.You may check either or both of the options 'Match only checked items' and 'Live updating' - in my experiments these had no effect.
8. Click 'OK' and name your smartlst '100 Newest' or anything you'd like.
Here's something to note:
In your iTunes 'Music Library', the sort order is newest song at the top of your library when the LIBRARY is sorted by 'Date Added' and the small triangle has it's apex pointing down. To me this means the LATEST song is on top.
In your '100 Newest' playlist, to sort so the newest song is at the top of the playlist when the PLAYLIST is sorted by 'Date Added' , you'll note the triangle is oriented with the apex pointing up. To me this signifies the 'YOUNGEST ADDED' song is on the top.
However you view those two items, it's interesting that you'd expect the sort order might be reversed according to the triangle orientations, but it's not. And that's one of the sorting problems I had with syncing my playlists - newest were on the bottom on my iPhone playlist, but on the top in the playlist in my iTunes Library. Certainly not a consistant user interface.
Also note that if you've used a previous hint in referencing a dated order playlist to avoid a previous iTunes playlist syncing bug, those lists now won't sort properly any longer. As I said - cut your losses and start anew.
Hope this helps someone else. It took me a long time to get right.