Hi Trisk Spellian. I had a similar problem with all outgoing email (not only attachments).
I was able to 'fix' this by forcing Icedove to version 31.2.0 (in Synaptic, select Packages => Force version).
Not sure if this is recommended as a solution by more experienced users, but hope it can help in your case.