How can I "relink" a lot of broken symlinks?

There is no command to retarget a symbolic link, all you can do is remove it and create another one. Assuming you have GNU utilities (e.g. under non-embedded Linux or Cygwin), you can use the -lname primary of find to match symbolic links by their target, and readlink to read the contents of the link. Untested:

find /mnt/home/someone/something -lname '/home/someone/*' \
     -exec sh -c 'ln -snf "/mnt$(readlink "$0")" "$0"' {} \;

It would be better to make these symbolic links relative. There's a convenient little utility called symlinks (originally by Mark Lords, now maintained by J. Brandt Buckley), present in many Linux distributions. Before the move, or after you've restored valid links as above, run symlinks -c /mnt/home/someone/something to convert all absolute symlinks under the specified directory to relative symlinks unless they cross a filesystem boundary.

I know this is not exactly what the author is requesting but it seems they already have their answer so I'm adding this for others like me who stumble upon the question.

The following should help if a more flexible solution is required such as having a bunch of broken symbolic links which can be fixed by replacing part of the symbolic link's targets.

eg. After a change of username, to replace the old username with the new username in the target of many links, after the move had already been done. Create a script called replace-simlinks shown below:

#!/bin/bash
link=$1
# grab the target of the old link
target=$(readlink -- "$1")

# replace the first occurrence of oldusername with newusername in the target string
target=${target/oldusername/newusername}

# Test the link creation
echo ln -s -- "$target" "$link"

# If the above echo shows the correct commands are being issued, then uncomment the following lines and run the command again
#rm "$link"
#ln -s "$target" "$link"

and call it with the following command:

find /home/newusername/ -lname '/home/oldusername/*' -exec ~/bin/replace-simlinks {} \;

Hope this help somebody

edit: Thanks Gilles for the kickstart on this script and the tip about using the symlinks script to make the links relative.

Create /home as a symlink to /mnt/home, and all the existing symlinks will be valid again.