I had this same problem now and saw this thread... If anybody has this problem in the future, I made it work by replacing the o-ring of the paintball tank that was pretty hard, and adding some food grade lube.
I noticed that if you tighten it too much the o-ring can rip apart and make thing even worse.
Also, when connecting to the regulator side don't forget the nylon washer. That one is pretty important... I also used teflon tape on the regulator side (on the tank side food grade lube only as mentioned above).
I hope this helps