I usually have a hard time connecting to VPN over public wifi, even when I use servers that are designed to be connectable even if there's a firewall in the way. This is true of servers I've set up myself and it's true of servers from commercial VPN providers like HideMyAss. Even if there isn't active manipulation or blocking from the firewall, it just seems that the connection is rarely strong or consistent enough to keep the tunnel from breaking all the time.

I have had better luck with a SOCKS proxy hosted at my home, but it's still not as good as VPN.