Setup->Company->Email Prefs->Domain Keys tab->Verify DNS entry. It gave an error. NS support had me generate a new key pair and DNS entry and I sent it along to our linux admin.