You could create the new link with a different name, then move it to replace the old link.
ln -s /location/to/link linkname
Later
ln -s /location/to/link2 newlink
mv newlink linkname
If newlink and linkname are on the same physical device the mv should be atomic.