This error occurs when you try to relink a file, but you choose the wrong one in the relink dialog. So for example file “A” is shown as missing. You click the exclamation point to relink it, but instead of choosing “A” at its current location, you select “B” by mistake. Because “B” is already in the catalog, you will get this error.
Another possibility is that you reimported the file before you tried to relink it. Because you reimported it, Lightroom now has two catalog entries. The original entry that you try to relink, and the new entry. Because thay new entry exists, you get the error when to try to relink the original entry. The only way to solve this is by removing the newly imported image from the catalog again before you try to relink the original entry.
You say you moved files around. If you moved a folder of files, rather than individual files, then it’s much better to relink the entire folder, instead of the individual files. It should show as ‘missing’ (name in italics and a question mark). Right-click on it and choose ‘Find Missing Folder’. In the dialog that follows, navigate to the current location of that folder on the hard drive and select it. Done.