This is stupid that I even have to post this. As mentioned here, Apple has released an update that fixed the "Smart Playlists stop updating dynamically on iPod". But you can’t simply update and have it start working. You need to do a "restore" on your iPod and resync all your songs. I’m guessing it was some kind of sync bug where iTunes and the iPod were miscommunicating, so the songs and smart playlist need to get recopied after the fix. Regardless, Apple shouldn’t just say "this update fixes it" – they should be clear about what additional steps are needed. Hopefully, someone else that runs into this will find this post using a web search and avoid the trouble I had getting my smart playlists to work again.