It happens after some firmware upgrades or hard resets. Erase the music from the watch MUSIC directory and then reload it through Garmin Express
Yes, this is a workaround but still doesn't eliminate the problem that the "factory reset" doesn't actually do what it's supposed to do. So per the OP, this is an issue with the firmware (maybe 5.1, maybe earlier). Just reporting.
Even the 'hard reset' does not erase all the data, you would have to manually delete the contents of \Garmin and \Music directories and then do the reset ;) It is not a firmware problem
