Yo creo que debe estar relacionado con el problema que comentas sobre tu antiguo servidor en febrero.
Cita:
Iniciado por fjbailon 
La verdad es que en febrero tuve problemas con mysql y el servidor y tras casi una semana de errores, decidi cambiar de servidor.
Creeis que esto tambien ha podido afectar?
Si el spider de Google detectó errores a menudo en sus intentos de rastrear su sitio, probablemente haya penalizado a tu web de algún modo. Entonces creo que es solo cuestión de tiempo para que al ver que la puede rastrear correctamente de nuevo, confíe de nuevo en el sitio.
Para ayudarle en el rastreo puedes hacer un fichero sitemap, si no lo tuvieras ya. EN dicho fichero puedes indicar la importancia relativa de unas páginas respecto a otras.