De que color son las letras de tu recovery???
otra razon puede ser que tengas mal configurado el apn.
en el tuto pasos para___2___froyo que esta en mi firma tienes una seccion donde estan las apn de distintas operadoras. echale un vistazo a ver si lo tienes igual.
ajustes - conexiones inalambricas - redes moviles - nombres de puntos de acceso abresla que tienes y en tipo de apn al final pone internet+mms ????