Apparently this has been happening for ages (at least going back to iTunes 7.x) and it appears to be related to sync operations not happening correctly/normally/whatever (although I didn’t perceive any sync problems on this particular phone).
As unexpected of a workaround as it is, I got lucky and ran across someone else that hit this today with their own iOS 5 upgrade. Just drag a new song not currently on the device from the library onto the device, and sure enough, that did the trick. The particular song synced over when I dropped it, and that triggered whatever necessary sanity check code that then resynced everything else on the device. Yay!