What should I do when I got the KEYEXPIRED error message after an apt-get update?

To find any expired repository keys and their IDs, use apt-key as follows:

LANG=C apt-key list | grep expired

You will get a result similar to the following:

pub   4096R/BE1DB1F1 2011-03-29 [expired: 2014-03-28]

The key ID is the bit after the / i.e. BE1DB1F1 in this case.

To update the key, run

sudo apt-key adv --recv-keys --keyserver keys.gnupg.net BE1DB1F1

Note: Updating the key will obviously not work if the package maintainer has not (yet) uploaded a new key. In that case there is little you can do other than contacting the maintainer, filing a bug against your distribution etc.

One liner to update all expired keys: (thanks to @ryanpcmcquen)

for K in $(apt-key list | grep expired | cut -d"https://serverfault.com/" -f2 | cut -d' ' -f1); do sudo apt-key adv --recv-keys --keyserver keys.gnupg.net $K; done