Should I change the private key when renewing a certificate?

I would say that their suggestion isn't a very solid one, unless you're using horrifically small key sizes - in which case you have a different problem altogether.

A 2048-bit key, by most estimates, will keep you safe until at least the year 2020, if not longer than that. If you're running with 1024-bit keys or less, you're below the standard, and I recommend updating to 2048-bit immediately. If you're currently using 1536-bit keys, you should be safe for a year or two.

Of course, this is all academically speaking. The likelihood of someone being able (or inclined) to crack your 1024-bit SSL key within a year is extremely low.

As mentioned in the question you linked, there are benefits and drawbacks.

Benefits

• Gives an attacker less time to crack the key. Somewhat of a moot point if you're using reasonable key sizes anyway.
• Halts any evil-doers that may have compromised your private key. Unlikely, but unknown.
• Gives you a chance to increase your key size to be ahead of the curve.

Drawbacks

• Doesn't really give you any concrete protection against key cracking unless you're using terribly small keys.
• SSL checking / anti-MitM plugins for browsers might alert the user that the key has changed. This is, in my opinion, a weak drawback - most users won't be using this.
• Might cause temporary warnings in relation to more strict HSTS policies and implementations.
• It requires work. You could be doing something else.

So on both sides there are some weak reasons, and some corner-cases you might need to consider. I'd lean slightly towards the "don't do it unless you need to" angle, as long as you're using 2048-bit keys or higher.

The most important thing is to ask them why they think it's necessary - it may be that you have an infrastructure-related reason for updating the keys which we don't know about. If they can't come up with a solid argument ("why not?" isn't really valid) then they should probaly re-evaluate their advice.

Changing the private key is not a best practice, it is a widespread practice; it has in fact very little to do with security, and a lot to do with how common CA handle certificate renewals, i.e. most of the time like a new certificate, with a new private key generation. It is simpler, on the CA side, not to do anything special for a renewal. Hence the habit of changing the keys.

The same sysadmins will not insist on generating new keys yearly for their SSH servers, even though the situation is similar, from a security point of view. Or, more precisely, changing a SSH server key is a bit inconvenient since it breaks the .ssh/known_hosts files of clients. Therefore it is customary to avoid changing SSH server keys. Thus, SSH server keys are long-lived. Nobody really skips a heartbeat on that. Why should they worry about SSL keys of similar cryptographic strength ?

The best practice is to change the key when technological advances have made your key somewhat vulnerable, taking into account the general paranoia (often called "for compliance reasons"); so you would consider that right now, in 2013, a 1024-bit RSA key ought to be replaced with a longer one, even though we are still far from being able to break such a key. If your RSA key is 1536-bit or wider, there is no cryptographic reason to make a new one (but, there again, maybe it is just more convenient to change it, on the CA side).

The answer is not technical or crypto, it's about people. With things like job changes (heard of disgruntled admins?), server migrations, DR tests, backups and such the private keys can become a bit exposed.

Given the above, key renewal is a security best practice.