Did you change the air fitting? It sounds like something might be restricting the air flow before it gets to the reg.
I had taped up a fitting and installed it with the loose end of the tape covering the opening one time, try and diagnose that, lol.
Another time I installed a swivel fitting with a braided hose. Turns out the fitting allowed the hose to go so far in that it covered the internal passage way about 50%. That was another head scratcher.
Take a second look, may be worth it.