Calma, calma, la primera regla del SEO es la paciencia. El sandbox es algo distinto, no es tan habitual como se dice caer en sandbox. Lo que ocurre con la web es normal, es nueva y existen muchas explicaciones. La más positiva es que consultastes un centro de datos distinto y aún no está actualizado. La más negativa sería que la web no es relevante, por falta de contenido (por ejemplo es una página en construcción) y Google la borró. Esta opción es poco probable últimamente Google no borra ni las páginas redireccionadas.
No vayas a cambiar de ip, no lo necesitas. Conseguir algún enlace puede venir bien, sin abusar.