Una de las causas del error es que no estés usando para la conexión de datos el APN que viene por defecto en la operadora.
En Vodafone el APN se llama INTERNET.
Por ejemplo, si has liberado el móvil para usarlo con Pepephone como me pasaba a mí, te va a dar ese error a menos que configures el APN "INTERNET" igual que el que te envía pepephone. Lo malo es que hay un bug cuando haces eso que ya no te deja acceder a los settings del APN, aunque todo funcione correctamente, incluído el compartir internet.
Como curiosidad, en el móvil, dentro de /etc/customization/settings/com/android/settings/custom_settings.xml viene una clave "tether_dun_apn" que tiene el valor del nombre del APN que se usa para hacer el tethering.
Un saludo.