Well, it could be a massive and obscure technical issue, it could be that the phones have one version of 802.11 and the router and computer have another. The VPN fix seems to suggest the former, though. If your modem/router is rented from your ISP, I'd ask them to replace it, and explain the problem to them fully. If not, I'd try wiring a WAP to it and connecting phones to the WAP, but that's an expense.
EDIT: It just occurred to me that if you use the phone to Internet through Wifi and it stinks, and through a VPN service and it's fine with the same exact WiFi access point, it's just barely conceivable that someone is poking at your network or stealing your bandwidth. Not likely that someone would bother for so long, though. I...