Reading http://support.apple.com/kb/TS3182 seems plausible. But the details about your email server are missing.
We're running v4.5 of Mail and OX10.6.8, and are having trouble sending attachments. Mostly we send PDFs, and when I resave the file with a new name, it usually goes out fine. (though not always).
We only send email from the one computer, and so if I want to send a file from my PC, I drag it to the Mac over the network, and send it from there. At first, I thought it was just the PC files that were having trouble, but I now see that files created on the Mac are problematic as well.
Any ideas?
Thanks,
Liz Coleman

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic