Some people are still getting this in 2017 and myself included. There are a few possible causes to this issue. I have narrowed down the list of likely culprits as follow:
The song itself can be corrupted.
The song can be in the wrong format.
There exists a duplicate of the song somewhere in Phone memory and SD card.
There exists a glitched object reference to a copy of the song stored in the cloud.
Path length of the file / scan depth limit.
The first cause can be tested easily using “File” explorer app or another music player. If the song can be played at all then the file (at least its content) is not corrupted. In the event this is indeed the problem, replace the song with a fresh copy (playable on a different device) should do the trick.
If the problem persists, try copy the song via USB cable connected to a Windows 8.1 and above PC. Any song that’s recognized as audio file by Windows and is incompatible to Windows Phone OS will be reformatted upon copying via USB connection. A dialog box will appear with this option.
The third and fourth causes are also quite simple to test. Simply rename the file and (possibly) the track title using a tag editor software such as Mp3tag. If the song works again, track down those duplicates and delete them. Then, check all playlists for any references to the song and delete them too.
Path length / Scan depth
Finally, the last addressable cause is path length. I have a fair bit of experiences working with Nodejs on Windows and I’m well aware of the path length limit of the OS. It is safe to assume that as Windows Phone is the younger sibling of Windows, it should possess the same limitation (and possibly worse).
Given how Groove Music, the default Microsoft’s music player, works on Windows, the “shortcut” reference of the song its scan function created in an app storage as lengthy as “C:\Users\<username>\AppData\Local\Packages\Microsoft.ZuneMusic_<random hash>\LocalState\Database” can potentially hit Windows Phone’s limit with just a little nudge.
In any cases, this is my problem and shortening the path length by moving all files up one level in the hierarchy did it for me. So, instead of SD/Music/Album/song.mp3, it’s SD/Album/song.mp3 after the move. I suspect it has more to do with arbitrary depth scan limit in the programming code and not the path length limit but meh, who knows what the interns at Microsoft did to produce such a broken piece of software.
At least it’s free and not full of fitness ads.