iPos Shuffle Auto-Update

I have an iPod shuffle, and it's linked to a playlist that updates based on when I last listened to the songs in it. Simply, it changes each time I listen to a song either on my iPod or in iTunes.

This playlist is linked to my shuffle, and hence it should automatically lose the old songs and copy the new songs over once it's plugged in.

However, it seems to only update the last played and playcount, then it tells me that the update is complete. If I then click the autofill button, it will copy the new songs over to my iPod, but only if I click the button. I have the option to replace all songs when autofilling checked, so that's not the problem.

I had thought that the problem was that it was checking the playlist before it updated the last played field. If this were the case, it would see that the lists match and would not update any songs. However, when I listen to a song in iTunes, it will take that song off the linked playlist BEFORE I plug in the iPod. I'm still getting the same problem!

How can I set it up to automatically adjust the songs on the iPod? I want to be able to update my iPod entirely in the background so I don't have to continually check on it to see if it's doing its job. Right now, that's just not working.