Eu finalmente resolvi isso ontem à noite baixando o pacote manualmente do repositório do ondrej e instalando-o com o dpkg:
$ wget https://launchpad.net/~ondrej/+archive/php5/+files/php5-imagick_3.1.0%7Erc1-1%7Eprecise%2B1_amd64.deb
$ dpkg -i php5-imagick_3.1.0~rc1-1~precise+1_amd64.deb
Atualização: pacote não encontrado 404, este é o endereço correto: link