I also had this problem, and I can't believe mailx solved it!
I was beating my head up against the wall trying to figure this one out. And, after a bit of web searching, I came up on this page.
I figured, what do I have to lose?
After installing mailx, the tar backup script I wrote that would run perfectly fine manually but would never run properly with a cron worked beautifully. What a redicilous and obscure bug!