nickiishaw Hi Nick, what are you using ST2, ST3, what operating system and what devices are you on?
This helps to come up with a more accurate answer.
It sounds like you are on an older system using itunes as MUSIC is the todays standard.
From memory, if i had a few red songs i would repair my links by going to playlist manager chose the blue i circle for the playlist you have missing songs in, then select the red song and then repair link, this takes you to itunes library , find the actual song in itunes and select it to repair the link, from then on whatever your named song is in ST2 it will play the new link you have just chosen.
Now this is a pain in the A i know especially if you have 2000 songs.
The other aproach would be in Itunes create a playlist with these 2000 missing songs and then create a new playlist in ST2 and sync all the 2000 song at once.Then Delete all your red songs.
Changing Itunes songs tags is a Major sin in the old system i always feared changing anything in itunes and for that reason went to ST3 as it does not relie on external software to keep your songs in order.
I dont know your exact situation but if i was you and could afford to change everything to the updated system i would do it immediately as it will save you a lot of time wasted trying to fix something that will take a lot of time and still not guarantee it will not happen again.
ST3 holds all its used songs in its own folder once you load your songs they wont dissapear on you and you can easily rename song names and Artist info without any problems, you will soon get rid of using Music at all and just load your songs to ST3 as it is a much more powerful music player.
I stay away from time wasting software as TIME is my most valuable asset i own and i dont like wasting it.
Hope i helped in some small way.
Cheers Damir