I have been messing around with this on my Galaxy Nexus with Android 4.0.2 and have confirmed the following settings for VPNs to our corprate firewall.
PPTP over Dataplan CDMA -- Everything works fine
PPTP over Dataplan LTE -- Untested due to lack of availability where I live and work, will test at a later date.
PPTP over WiFi -- Everything works fine
L2TP over Dataplan CDMA -- Connection timeout
L2TP over Dataplan LTE -- Untested due to lack of availability where I live and work, will test at a later date.
L2TP over WiFi -- Everything works fine
OpenVPN
not supported without rooting the phone -- Verizon please add this functionality into your base ROMs for all of your phones.
The reason I ask about anyone coming across this or having a fix is PPTP may work but it's old/insecure comparitively and may be going away in a future stable tree release of the corprate firewall I work with. The full support of L2TP and/or OpenVPN/SSL-VPN would make life a lot easier for us techs who need to bounce into a server quickly and do what's needed when having a PC at hand is impossible, ie at a sitdown resturant. If you need logs of the connect attempt let me know and I'll get them to you. I did however see this error posted on the Samsung Fascinate forum as well.