I would have opened in Illustrator for both steps 2&3. Photoshop makes you choose a rez and render out certain elements when opening a PDF correct? Seems like it would cause less of a change in the file if Illustrator was used. Depending on whether the image you needed to replace was placed separately, or if the whole page is a single image. Even if it was a single placed image, id copy and edit the image in photoshop then use place to drop it back in Illustrator.
Can someone confirm?