Do you feel spring tension when you pull the ring on the relief valve? And does it pull out about 1/4"? It should have both tension and pull about 1/4" or so.
Another trick to try is to pull the relief valve's ring and let go of it quickly. Sometimes they stick open and that tends to seat the seal a little bit.
If that doesn't do it, is the pressure gauge building when the relief starts blowing?
Every once in a while my regulator starts climbing uncontrollably and the relief starts letting excess pressure out. I have to shut the tank off, and release any pressure in the system, then turn the tank back on slowly to fix that.
You could also have a bad regulator, or relief valve also. Don't rule that out just because it's brand new.