A discussion was had on one of the Fedora IRC channels months ago about the "proper" way to handle expiring GPG keys without breaking the web of trust. It was my opinion that by generating new keys every so often (yearly?) that it would increase the security of the overall system because keys can be cracked and the longer the key is in the wild the higher the chances of the key being exposed. You may not even know that they key has been cracked or being used.
Today I went searching for answers and found them in a keysigning HOWTO. The HOWTO explains, what I would consider to be, a valid reason to regenerate your keys along with a proper method for not necessarily breaking the web of trust.