La procedura che hai indicato è corretta ma, come diceva passante, i sintomi che descrivi fanno pensare che le cose non siano state fatte correttamente.

Due domande:
- se digiti nel browser il vecchio indirizzo della pagina cosa succede?
- con che tecnica hai creato il redirect 301 dalla vecchia alla nuova url?

Potrebbe anche darsi che sia solo questione di tempo, anche se sarebbe strano a mio parere.