The music application on iOS has, for me, always been one of the most stable applications and not something I've ever had to think about. I create my playlists in iTunes, sync to my devices and listen to music.
However since iOS 5 I've been experiencing issues with smart playlists and just when I thought iOS 5.1 had fixed it the bug appeared again. My smart playlist is relatively simple and lists songs rated between 3 and 5 stars that I haven't listened to in the last 3 months.
But when syncing to iOS devices it'd either have no items, sync a random number of items or even have items on the device that aren't listed in iTunes. Thinking it might have been iTunes Match causing the problems I disabled it on iTunes and iOS without any luck.
After some Googling I came across this post describing the exact same issue I'm experiencing. Turns out the solution seems to be to set a new rule of "Playlist is Music" which solves it. I've no idea how long this will last for but right now things are syncing perfectly.
My current configuration is an iPhone 4 running iOS 5.1 and iTunes 10.6 (40) 64bit.