Q: Moved my iTunes library and reinstalled OS X, now some songs cannot be located because of weird path So I moved my iTunes library to an external HDD using the Apple KB article just fine. Then I created a symlink from /Users/myuser/Music/iTunes to /Volumes/external/Music/iTunes and that worked just fine as well. Then I erased that system completely and clean installed OS X Lion. I recreated the symlink on the new install and fired up the latest version of iTunes 10.4 (80). 
Now some of the songs cannot be located. If you use get info in iTunes the files that work all have the path like /Volumes/external/Music/iTunes/.....
The files that cannot be found use a path like
file://localhost/Volumes/external/Music/iTunes/....
Oddly enough the library xml files uses paths that all have the file:// convention, but I know iTunes doesn't actually use this file directly. The "broken" paths are all completely valid, but iTunes sees these as missing. 
I think I found another pattern. In the library xml file all the tracks that are broken in iTunes have the following tags where as the working tracks omit them.
<key>File Folder Count</key><integer>5</integer>
<key>Library Folder Count</key><integer>1</integer>

How can I (easily) fix this?

A: Did your library start out as self-managed and somewhere down the line you switched to having iTunes manage it ?
I have my library on an external drive too (under Lion although I didn't start from scratch like you), why are you using symlinks? ITunes can run a library off an external drive without them.
If you close iTunes and hold down Option when you open it again you will get prompted to select an iTunes library, navigate to the actual library file on the external volume ( not via a symlink) and see if that works.
