I first tried to export a collada file but then I read that maybe my objects are not plain.
So I did what I usually do when I check my stl files for 3d printing, I repaired them, and then re-exported them through collada and Imported then into Blender.
Unfortunately, I still can't do the subtraction.
Surely somebody here will tell me what's wrong? Maybe the whole approach?
I attached the blend file (2.6 version) so some charitable person could have a quick look and spare me light years of trial and error?
Resolved. Thanks to @Mr Zak for his help! (See second comment)