As I recall, I had issues with Relink to folder, and it was because I was including the extension...
Were you able to relink your files but with a different extension then? I'm having the same problem, but on Mac OS X 10.9.3 and ID CC latest update. If I try to relink a bunch of images (psd or jpeg, doesn't matter) to same files but in Tiff, I get the Fail to relink message. It was working fine before but I don't know if it's the latest OS update or something else that broke it. It happens on all our macs at work as well. Hope you have found a solution and are willing to share it!
It's been a long time since I tried to do any relink to folder, and I wasn't trying to change the format as far as I can remember.