That's about the shortest title I could think of to be descriptive of this issue. TLDR is that NAT rules on vShield Edge appliances appear to be causing unexpected behavior on VPN traffic after a vCloud upgrade from 1.5 to 5.1.
While vCloud Director doesn't show anything strange in the firewall section of vSE configuration, if you log in to vShield Manager and look at the firewall rules there, a "Deny" rule with the private/internal/translated IP is added for any NAT rule that exists:
This, I'm assuming, is for security reasons during the upgrade but it does not show up in vCloud Director (thus our confusion). After taking our appliances out of compatibility mode post-upgrade, the rules were still there.
Solution: After the vSE is out of compatibility mode (see pg. 49 of the vCD 5.1 Install Guide), re-apply the service configuration (Right-Click vShield Edge Appliance in vCloud Director and select "Re-Apply Service Configuration"). You can also re-deploy the appliance or add an arbitrary rule to the firewall list - both appear to have the same effect.