You can turn relative paths into full paths using readlink -f foo. So you would do something like:
ln -s $(readlink -f $origlink) $newlink
rm $origlink
EDIT:
I noticed that you wish to keep the paths relative. In this case, after you move the link, you can use symlinks -c to convert the absolute paths back into relative paths.