DNS Help

My Qmail is not happy with the domain: ftae.com And I was hoping that
someone on the list can help me identify. I've been running qmail for
years with few issues. Here is what I see in the logs:

Mar  7 21:34:59 mail qmail: 1299551699.837829 starting delivery 19: msg
23365568 to remote [email protected]
Mar  7 21:34:59 mail qmail: 1299551699.837919 status: local 0/10 remote 5/20
Mar  7 21:34:59 mail qmail: 1299551699.915753 delivery 19: failure:
Sorry,_I_couldn't_find_a_mail_exchanger_or_IP_address.
_(#5.4.4)/

Their DNS appears valid, but I'm no dns expert. I validated them with this
site: http://www.dnsvalidation.com/ and it seemed ok. I tried dig, and
compared with my own server:

dig @208.67.222.222  +nocmd ftae.com any +multiline +noall +answer
ftae.com.		0 IN A	67.215.65.132
ftae.com.		3240 IN	MX 10 mail.ftae.com.
ftae.com.		3240 IN	NS ns1.paetec.net.
ftae.com.		3240 IN	NS ns3.paetec.net.
ftae.com.		3240 IN	NS ns2.paetec.net.


dig @ns1.paetec.net  +nocmd ftae.com any +multiline +noall +answer
ftae.com.		86400 IN SOA dns-master.paetec.net. dns.paetec.net. (
				36         ; serial
				28800      ; refresh (8 hours)
				14400      ; retry (4 hours)
				604800     ; expire (1 week)
				86400      ; minimum (1 day)
				)
ftae.com.		3600 IN	NS ns3.paetec.net.
ftae.com.		3600 IN	NS ns2.paetec.net.
ftae.com.		3600 IN	NS ns1.paetec.net.
ftae.com.		3600 IN	MX 10 mail.ftae.com.

dig @ns1.paetec.net  +nocmd mail.ftae.com any +multiline +noall +answer
mail.ftae.com.		3600 IN	A 74.10.239.236

dig @ns1.cttechhosting.net  +nocmd cttechhosting.net any +multiline +noall
+answer
cttechhosting.net.	3600 IN	TXT "v=spf1 a mx"
cttechhosting.net.	3600 IN	A 66.135.59.179
cttechhosting.net.	3600 IN	SOA ns1.cttechhosting.net.
webmaster.cttechhosting.net. (
				2009111206 ; serial
				3600       ; refresh (1 hour)
				120        ; retry (2 minutes)
				604800     ; expire (1 week)
				3600       ; minimum (1 hour)
				)
cttechhosting.net.	3600 IN	NS ns1.cttechhosting.net.
cttechhosting.net.	3600 IN	NS ns2.geodns.net.
cttechhosting.net.	3600 IN	NS ns1.geodns.net.
cttechhosting.net.	3600 IN	MX 1 mail.cttechhosting.net.

The biggest difference I see is their MX is set to 10 instead of 1 - is it
possible that could be making qmail choke?

Thanks for any help,

Russ