I wouldn't take it apart yourself unless you have the proper tools and knowledge. Since this is your primary reg, you're just asking for more trouble. Practice on an old reg to learn.
After I posted that, I was thinking I should see if I could find a cheap one on e-Bay to play with.
You didn't mention anything about cold so I'm guessing it couldn't have been blocked by ice. And I'll assume you know for sure the air was actually on and the hose wasn't kinked.
78 degrees water temperature, so ice is not likely. Air was on - that was my first thought. If I hadn't been able to replicate the problem the next morning, after removing, rinsing, and reinstalling it on a different tank, a hose kink could have been the problem, since I didn't check specifically for that at the time of the incident.
It could have been debris in the first stage blocking the port.
Probably not likely - the replacement reg worked for 2-3 dives immediately following the morning replication of the problem and the swap out of reg only - not the LP line. I would think if it was debris, it would have locked up the replacement second stage since there wasn't any significant movement that would have dislodged it before I tested the replacement reg.
I'm still leaning towards improper parts or assembly during the original service. I don't know anything about your LDS but I can see where an LDS would not want to admit they seriously botched a service job that could have had catastrophic consequences if they could quietly fix things and ensure it doesn't happen again.
I think I want to see if I can figure out what might have caused the sound/feel of the incident before I go down that route - if the innards are as straightforward as the explanation I posted earlier, I'm having a hard time figuring out what I heard/felt.