This happened to me to about 500 songs. Restart didn't fix it but I found that if I did 'get info' for the songs, the song titles magically reappeared.
So I basically arranged the library by name, went to the first nameless song get command+I and then did the keyboard shortcut for next song loads of times....
Took about 30mins but it fixed it...