The practice of taking a new name began not to honor a predecessor, however, but to avoid an embarrassment.
After the death of Pope Boniface II in October 532, there was a two-month vacancy in the position. Part of the reason for this was a (ahem) change in the process. You see, it had become common for some candidates to ensure their election through bribes and gifts. The Roman Senate forbade this practice just before the death of Boniface. Athalaric, the King of the Ostrogoths in Italy, upheld the Senate's decision, and added his own flourish: a disputed papal election that needed to come before his court would be fined 3000 solidi (a solidi was a gold coin of 4.5 grams) and the money given to the poor.
The cardinals fell into agreement on a distinguished priest of Rome, aged about 60. He was willing to take the job, but he had one concern. His Roman parents had given him a theophoric birth name—a name that honors a god in order to impart luck and protection to a child. His name was Mercurius. Father Mercurius did not think it was appropriate for a Christian pope to bear the name of a Roman god. He decided to take the name of a pope from a decade earlier who had had a good working relationship with Athalaric's grandfather.
And so Father Mercurius became Pope John II, the first pope known to have taken a new name upon election.