I have this problem intermittently, and also intermittently have a problem where Mail can't communicate with the Icloud server, so I can't download new mail or send messages to others. My email address is my old mac.com address, and Mail still displays "For support, visit MobilMe" at the bottom of the accounts preferences. The link to MobileMe takes me to the "MobileMe is closed" webpage.
MacPro, OS 10.7.5
Assuming that your operating systems are as steated in your signatures, you both may find it helpful to remove the account from Mail Preferences/Accounts and then set it up again following the instructions here: