Como han apuntado, debe de haber conflicto de direccionamiento IP. Android no tiene por qué funcionar de la misma forma que iOS, con lo cual el hecho de que un servicio funcione con un iPhone no tiene nada que ver con el funcionamiento del Samsung S5. Al hacer tethering, el teléfono se convierte en un router que ofrece un rango de direccionamiento IP en la interfaz que va al ordenador, y recibe un rango de direccionamiento IP en la interfaz de datos (3G/4G) moviendo los paquetes entre ellas.
Al forzar una VPN en el proceso, los datos se encapsulan para que viajen por la VPN. Si el rango de direcciones IP que proporciona Vodafone, pudiese tener algún tipo de incompatibilidad con el rango de direcciones de la VPN o el rango de direcciones ofrecidas por el mecanismo de tethering, explicaría el problema. Como desconocemos cuáles son los rangos de direcciones implicadas en todo esto, es complejo darte una respuesta satisfactoria.
La causa podría ser que la VPN fuese incompatible con Vodafone. No has confirmado que en el iPhone funcione la VPN con exactamente la misma tarjeta SIM de Vodafone con la que el Samsung S5 esté fallando, lo que descartaría que Vodafone bloquease la VPN. Tampoco sabemos si el tethering proporciona el mismo rango IP en un teléfono que en el otro, ya que son sistemas operativos diferentes y sus resultados podrían ser diferentes.
Al hacer que un móvil funcione como router, las direcciones privadas ofrecidas en la interfaz que va al ordenador podrían entrar o no en conflicto con la red configurada en el sistema operativo del ordenador, que no has especificado. Hay una gran variedad de rangos, y existe la posibilidad que Android use unos e iOS use otros diferentes. Es lo que naveganteperdido intentaría decir. Es posible que tal vez esos parámetros fuesen configurables en los ajustes del teléfono, pero es tirar los dados al aire sin más información concreta.
