My mail is hosed, why?

Do you have an MX record with no A record?
example:
% host example.com
example.com has address 1.2.3.4
example.com mail is handled (pri=0) by mail.example.com

% host mail.example.com
Host not found, try again.

solve this by adding an a record for mail.example.com

do you have an a record for your zone?
% host mail.example.com
Host not found, try again.

solve this by adding an a record for example.com.

Do not put a CNAME in the rdata section of a MX record.