Me pasaba sino lo mismo algo parecido. Instalaba recovery y al reiniciar e intentar ir a recovery me saltaba el antiguo.
Cuando haces recovery y te arranca la primera vez, te pregunta si quieres flashear el recovery, yo le decía que no por miedo (soy novato). Si le dices que si, ya esta.
Otro compi dice que quitando la batería y algún paso mas entra en el nuevo tambien, pero a mi no e hace falta
.
A ver si te ayuda, salud!