I've started getting those also. I set up an account at
http://www.gmx.com/ in order to use their services. Things seem to work fine as soon as I went into my kindle profile (on amazon.com) and added the new e-mail address and likewise, my GMX account as the default account to send from with Calibre.
Good luck