Bueno, pues gracias a un amigo, me respondo a mi mismo y os lo pongo aquí por si os llega a suceder.
Ir a "Menu"-"Ajustes"-"Aplicaciones"
Buscar la aplicación GooglePlay (antes el Market)
Darle a "borrar datos" y a "borrar caché"
Reiniciar el teléfono
Y me ha funcionado. Parece ser que hay quien ha tenido además que desinstalar las actualizaciones del Google Play (está en el mismo sitio) y luego reiniciar.
Ojalá os sirva si os surge el caso.
Un saludo a todos.