I've had this happen to me, too. I found that if you try to set up MX records *immediately* after you have set up the CNAME, this problem seems to happen, because the CNAME has not percolated through the system. You are working on a DNS system which is a long way removed from the Web Browser you are entering data from, so give some slack!
Give it a while and try again...though reading your post again, if nslookup resolves, the above may be a total load of rubbish
HTH
Jimbo