Como dito, o problema era ter / tmp montado com noexec. A explicação é bem simples, alguns scripts de instalação descomprimem executáveis / scripts em / tmp e então tentam executá-los.
Eu realmente tropecei nesse problema também por acaso algumas luas atrás, quando mudei em alguns servidores / tmp para ser noexec por razões de segurança, e então os scripts de instalação / atualização de alguns pacotes Debian pararam de funcionar. Como eu mudei de propósito, foi muito fácil identificar o problema no momento.
Eu ainda acho que é uma boa idéia definir / tmp para noexec em servidores web públicos, no entanto até agora eu não pesquisei muito como contornar este problema em particular.