So, I had just installed a new ROM and tried to restore all my apps using Titanium Backup. It was routine stuff, nothing I hadn't done a thousand times before. While restoring Authy, TiBk was stuck for a long while and I didn't want to wait.
I remembered that last time TiBk was stuck while restoring an app, Installing the same app from Google Play Store while TiBk is still running seemed to have worked. So I did just that. I let TiBk run while I installed Authy from Play Store. Play Store finished installing Authy and TiBk also finished restoring Authy right after.
Now, when I tapped on Authy, it wasn't opening up. Naturally, I tried to Wipe Data and Cache for Authy and tried installing the app again. However, Play Store started complaining that it couldn't install Authy and asked me to try again after sometime. At one point it even told me there wasn't enough space on my phone. I also tried wiping data and restoring App+Data using TiBk. Nothing seemed to work.
On a whim, I opened up Root Explorer and deleted everything related to Authy under /data/app and /data/data folders and tried re-installing Authy from Play Store and that did it.
One thing I did notice was this symbolic link pointing to itself in one of these directories:
I don't know how that's possible. I should have taken a screen print but I didn't.
There you go, I hope this helps. While this worked for me, I do not guarantee it will work for everyone. YMMV.