They reasonably thought they were on Ceti Alpha VI because that had been it's orbit. Space is a very large and busy place so obviously Stellar Cartography is kept very busy.
A single planet taking another's place in orbit in a remote solar system could be easily missed.
It's possible also that the star chart could have mistakenly logged the surviving planet as Ceti Alpha VI and removed Ceti Alpha V as being destroyed. No one had been back to confirm this apparent fact since Khan and company had been placed there. They obviously had no idea that it was in fact Ceti Alpha VI that had been destroyed and it's orbit taken over by Ceti Alpha V. Who knew? Thinking that Ceti Alpha V was destroyed is reasonable due to it missing from it's orbit.
The kind of planetary 'musical chairs' that occurred is obviously very rare so their surprise by such an unusual/rare occurrence would be a reasonable reaction.
Chekov though, being there firsthand when Khan was marooned, was quick to put 2 and 2 together and recognized their danger after seeing the ship's name, 'Botany Bay'.