This seems to be a problem that a few people are having. I have DHCP set up on a Windows 2008 server. Amongst all the options I have set, is option 121 (Classless Static Routes). I have two routes set up going over two VPNs, one to one datacentre and one to another, both going through different gateways.
We have a wifi network here with no restrictions to the network once you're connected to it.
The Android devices connecting to the wifi can connect to machines going over one of the routes, but not the other.
The Windows PC I'm currently typing this on also gets its IP address from the same DHCP pool and I have no issues with connection to machines in both datacentres.
Just in case it's useful to know, the DC that I can't seem to connect to is Amazon Web Services.
My device is a Samsung S4 with 4.4.2