This problem seems being solved by means of 2 different ways, this is described at http://www.debian-administration.org/articles/57 First one is to use DPkg::Pre-Invoke and DPkg::Post-Invoke to remount the /tmp partition with execution permissions during the apt operations. Second is to use another temp dir for APT with the APT::ExtractTemplates::TempDir option. I guess the bug can then be closed. Antoine.