VPN over 3G with Verizon?

I've tried everything I can think of, but my VPN will not connect over 3G. When I use Wi-Fi, it connects great, but over 3G it gets stuck and always times out. I called Verizon Technical Support, and they were close to useless. I tried the trick floating around where you change your features from "NAT IP" to "Generic IP," but that didn't make a difference. Has anyone been able to connect to PPTP VPN over 3G with Verizon? If so, how did you accomplish it? Thanks!