Yes, it is really weird.
Have you noticed marvinuk's comment?
Finally got it working, we are currently using sql server 2008 r2 which doesn't seem to support .net 4 therefore when referencing rebex I can only use v2.0, which means I have to resister the dll in the old gac in c:\windows\assembly. To do this on server 2012 I had to install the 3.5 .net sdk so that I could use the appropriate gacutil.
Please ensure, you have all necessary Rebex assemblies in correct GAC.
I also found an article, which can help you solve the problem.