I have the config up and running without issue now. It was a couple of weird settings I had to apply in my SonicWALL. You aren't using a SonicWALL are you? If you PM me more details I can assist.
For the sake of this thread, here is what I had to do:
1) In my outbound NAT policy, I had to change the 'original service' from my SIP+RTP group to "Any." Basically sending any/all traffic from the PBX out of the public IP address I was NAT'ing to, not just SIP/RTP. Something to do with the randomized port not being in the 10000-20000 range.
2) In 'advanced' under that same NAT policy, I had to check 'disable source port remap.'
So far, this has fixed my issue on every occaision. Some of my SonicWALLs didn't have those options, but updating to the newest firmware makes them show up and configuring as above fixes it.