Are the links all in one place, or scattered around the directory tree?
If you can create a list of the links somehow, it should be pretty simple to write a script to change them. A simple for loop using readlink and ln should do.
Code:
#!/bin/bash
for link in *.link; do
target=$(readlink $link)
ln -sf "/new/path/${target#../}" "$link"
done
exit 0
readlink outputs the current target path of the link. "${target#../}" should strip the first ../ directory section off the old target name, so you can tack on the new one. See
parameter substitution for other variable manipulation options.