Ah, it appears that video was the procedure to root if you were on ICS.
So, in my opinion, I think we need to go back to stock, unroot, then reroot.
Go to this link and go to step 5. I would choose the VRBLK3 4.1.1 file.
http://forum.xda-developers.com/showthread.php?t=1762709
Flash that file in ODIN.
After that flash, you will be unrooted.
Then follow this guide to root:
http://forum.xda-developers.com/showthread.php?t=2046439
Here is a video for that process:
How To Root Verizon Samsung Galaxy S3 4.1.1 & Install CWM Recovery! SCH-I535 - YouTube
I think that will get you back to where you want to be
If someone else can confirm this process, then joy will follow