Hola, a mi también me pasó cuando se actualizó el market con la versión que te aparecían banners con programas populares. Con el uso del market se me arregló sólo pero otra vez que me pasó borré el contenido de /data/data/com.android.vending que es donde se guarda la información del market. Hacer una copia de este directorio por si os peta. Después de borrar el contenido reiniciar, entrar en el market y aceptar de nuevo las condiciones.
Si así no se os arregla, paciencia, a mi me pasó la última vez hace unos días después de hacer un wipe y actualizarse el nuevo market y a la hora (después de hacer actualizar algunas apps) se arregló sólo.
Saludos.