Are your song files in more than one folder on the external drive? If so are all the folders listed in the rebuild database screen?
If so then check the following thread. This has to do with the Songbook, buit you can apply the same changes to the External drive folders to allow access to those files.
http://forum.mtu.com/showthread.php?t=9363