In OS X, my 512MB Shuffle doesn't automatically erase. Maybe something weird happened to your iPod's settings in the iTunes update from 6 to 7. Check over your iTunes and iPod settings. Check the iPod's AutoFill settings as well. Keep us updated.
Daniel.
EDIT: Just so you know, my Shuffle system that works for me is to never actually fill the Shuffle straight from the Library. I always make playlists. At any given time, my iTunes has several different iPod Shuffle playlists. At the moment, there's only two: "iPod Shuffle Favorites" and "iPod Shuffle Sleep." This makes it so I don't have to go through my library every time I want to find music. Mind you that I have 33GB of music and I bet I've only heard 75% of it, if even that, so the iTunes Autofill always gets songs I've never heard, so I don't use that.