I've been having a similar issue, and have a suggestion and would like to propose a question at the same time.
I have gutsy gibbon(ubuntu 7.10) running fully updated w/ virtualbox running WinXP SP2 as a guestOS. Before I installed the virtualbox Guest Additions I created two VPN connections to diff. networks I work with on a regular basis. Everything worked as it should very seamless. The firewall was manually turned off, and both connections had shortcuts on the desktop.
Now I installed the Additions to get the integrated mouse/keyboard action going, and on reboot there was only one VPN connection. Apparently the second connection had been deleted, and only one remained both in Net Connections and on the desktop. When I try and connect to the remaining VPN it connects and times out on Verification. Maybe im missing something in the setup, but it seams as if the Additions are presumably changing something in the Net setup as well. Another interesting point is that if I try and uninstall the Additions the system crashes on some sort of Kernel like panic that Microsoft vaguely attempts to describe, but in any case I guess the only alternative is to re-install the guestOS.
I'd say try and reinstall your XP and see if the VPN works out of the box, and see if you have the same results as I do. Maybe we can get something going. Let me know. I'm going to reinstall and check to see what the actual differences are.
As far as researching the problem I did do a search on the forum and didn't come up with much, but maybe I missed something in the manual. If I find anything interesting I'll post it on here.