Sounds like it may be a corrupt SIM card.
I remember back when I was playing with my old 4G phone that a corrupt SIM card resulted in the phone getting 4G but no 3G. Sounds weird? Well, that's the case. Replacing the SIM card resulted in both 3G and 4G working properly.--
Boycott AT&T uVerse! | Tom's Android Blog | Galaxy Nexus LiquidSmooth by TeamLiquid