You should be able to browse to the new location when that message comes up. There is a checkbox as well that says something along the lines of “remember path changes”. Checking that will fix up the reference paths to be correct on your machine.
Everything in the toolkit uses relative directory paths based on your install location. However, Maya’s referencing uses absolute paths 
I haven’t looked too deeply into whether or not I can catch that and change it automatically for the user. I’ll be adding that to my list for investigation.