Me respondo yo mismo. No era un problema del Tatoo o de Android. Vodafone Empresas había capado el envío de SMSs a todos los empleados de la empresa donde trabaja mi padre por error. Lo han arreglado ellos y ya funciona todo correctamente. Ya es casualidad que haya coincidido el cambio de móvil de mi padre con esta cagada de Vodafone Empresas...