How do I fix failed aliases?
Here's my stab at solving this problem with Applescript. The following applescript will take selected aliases in the Finder and try and relink them to the new path replacing Backup with External in the POSIX path.

Hopefully it's straightforward. You could probably make it recursive to search for aliases in selected folders, but that's more work than I care to do -- and then there's the problem of dealing with aliases to folders. Things could get messy. ;-)

Hope it helps.

tell application "Finder"
    set these_items to the selection
end tell

repeat with i from 1 to the count of these_items
    set this_item to (item i of these_items) as alias
    set this_info to info for this_item

    if class of this_item is alias then
        tell application "Finder"
            set original_file to original item of this_item
            set this_alias_file_name to displayed name of this_item
            set container_folder to container of this_item

            set the_path to the POSIX path of (original_file as alias)
            set new_path to my replaceText("/Backup/", "/External/", the_path)

            move this_item to trash
            try
                make new alias file at container_folder to (POSIX file new_path) with properties {name:this_alias_file_name}
            on error errMsg number errorNumber
                if errorNumber is -10000 then -- new original file not found, try relinking to old
                    try
                        make new alias file at container_folder to (POSIX file the_path) with properties {name:this_alias_file_name}
                    on error errMsg number errorNumber
                        if errorNumber is -10000 then -- old original not found. link's dead Jim
                            display dialog "The original file for alias " &amp; this_alias_file_name &amp; " was not found."
                        else
                            display dialog "An unknown error occurred:  " &amp; errorNumber as text
                        end if
                    end try
                else
                    display dialog "An unknown error occurred:  " &amp; errorNumber as text
                end if
            end try
        end tell
    end if
end repeat

on replaceText(find, replace, subject)
    set prevTIDs to text item delimiters of AppleScript
    set text item delimiters of AppleScript to find
    set subject to text items of subject

    set text item delimiters of AppleScript to replace
    set subject to "" &amp; subject
    set text item delimiters of AppleScript to prevTIDs

    return subject
end replaceText