Estoy en las misma, creí que me pasaba solo a mi XDDD
Probablemente hayan bloqueado el acceso al play store a dispositivos no certificados.
Entre esta noche y mañana quiero probar una historia que hay por ahí que usa el Market Enabler y una red VPN, a ver si hay suerte. En cuanto sepa algo lo comento.
EDITO: Comprobado el problema tanto en android 2.2 como en 2.3. Cambiar la rom no soluciona el problema.