The 'Time to change your encryptkey!' message displays in the admin site, and after trying to change the key the site reports that it was completed, but the message continues to display and the encryptkey does not change.

This can occur if an SQL error is encountered during the updates that are made when changing the encryptkey, or write permissions on the folder containing the web.config file are not allowed for the .NET user account.

Check the SQL logs (check with your host if you do not have access) for errors.  This can be a permissions issue, a result of bad data, etc.  The error will have to be corrected before the encryptkey will change. Verify write permissions on the folder containing the web.config file are allowed for the .NET user account (typically ASPNET for WindowsXP or NETWORK SERVICE for Windows Server 2003/Vista or IIS_IUSRS for Windows Server 2008/Windows7)