Google puede enviar mensajes a los 3 principales operadores móviles de Colombia, pero personalmente he tenido más problemas al verificar con un número de Comcel... Aunque quizás tarde más debido a la congestión o tráfico en esa red, pero si sigues teniendo problemas, intenta desde un número de otro operador o un número que tenga un plan diferente.
El número debe escribirse normal, sin espacios ni ninguna clase de indicativo o prefijo. Por ejemplo 312474XXXX