Did you change mail servers within the same provider, or did you switch to a different provider? If your provider has changed, did your email address change? If so, did you add the new email address to your key?
Are the settings and email address the same, just a change in mail servers? If so, you could try setting the mailservers as a wildcard character * and it should continue to work with the same settings.
Which protocols are in use for mail connections (POP, MAPI, IMAP)?