A purchased song? This seems to be happening a lot since the last update. My Nano started doing it too the other day.
If it is a purchased song, try unchecking it in the iTunes playlist, syncing the iPod so that it's not on it any longer. Then log back out of and into your iTunes account, recheck the song and resync the iPod. If that' doesn't do it, then you might have to restore the iPod.