Changing that setting in Preferences > Advanced only affects where iTunes will now store files when you add them to the library. All the links to the tracks already in your library are contained in the file called iTunes Library.itl (or on some systems, just iTunes Library) in the main Music > iTunes folder. The key trick with relocating an iTunes library to a new computer is to keep the original path from the .itl file to the media files absolutely intact.
Normally this is done by having the iTunes library in a "portable" condition -- i.e., with iTunes Library.itl and the iTunes Media folder both contained in a folder called iTunes on either an internal or an external drive. Is that how your library was set up before? Or was it (like mine) set up with iTunes Library.itl on the internal drive, and the iTunes Media folder on the external drive?
If it was the first case, then you should be able to load your library by holding the Option key down while opening iTunes, and navigating to the library file on the external drive. If it's the second case, then you'll need to copy the iTunes Library.itl file from the older computer to the new one -- replacing the file that's currently there, if there is one. Make sure the external drive is mounted on the new computer, and open iTunes. If all goes well, the links to your library should work. If not, please post a follow-up.