You must be doing something wrong, from your description hard to tell exactly what. Normally, links should be relinked just fine using commands from Links panel flyout menu.
Whatever, if you have all your new links in one folder (without subfolders), you can use 'brute force' method which always works.
1. Close ID document.
2. Rename or move your old working folder with links somewhere else.
3. Copy ID document itself to the folder with new links.
4. Start to open that copy. It must capture links with the same names/extensions from the same folder, where ID document resides, even without warnings.
5. If you want to have a working and properly linked ID document in other place, not the links folder, do a Save As or Save a Copy
That's it.