I re-synced a fresh copy of my achievement world to get access to a Notch apple for the purpose of getting the banner achievement (which has not popped, by the way), and in that world are my two cats. These two do not seem to suffer from the issues around the change of the player's internal ID, so I can still interact with them. One walked off and vanished, but the other remained in the base.

For two in-game days I have been trying to get the "Where Have You Been?" achievement, but the cat does not seem to be behaving like it should. It does not lay on the bed, merely sits on top of it, and there is no sign of it bringing me a present.

Do I have to go and tame entirely new cats to be able to get that achievement?