If I had infinite patience, I could go through the manual process outlined below. The key is to create a table which has one an entry for each note, containing the UUID in one column and the note's title in another. So:
Within the Evernote application, open a note and copy the internal app link. Paste this into a table (in some text file). Then copy the title of the note and paste this into the table.
Repeat for all notes.
Now you have a text file which has a table showing the UUID and title for all notes.
Export the notes
Open each exported note and search for links.
For each link you find, the UUID contained in the link, together with the table you have created, will enable you to look up the title of the note that is linked to.
Search for the exported note with this title. Change the link to point to this note.
It relies on each note having a unique title. But if this is not the case, the process could be tweaked by creating an additional column in the table containing date created.
My coding abilities are pretty much zero, but I would have thought that it should be possible to write a script to automate this.