I thought I'd just document it here for future reference (mine as well as others)...
It seems that some firewalls will randomize outbound ports. This can mess up certain protocols such as SIP. With SIP, if the source port for the REGISTER does not match the source port for the INVITE you may get an SIP error 403.
The solution is to statically map the ports for the NAT traversal. The solution to the problem is documented here.
Thanks to Jonathan for putting in the hard work!