Parece que este pacote está disponível no Repositório do Universo [1].
Primeiro, tente executar apt-get update para ter certeza de que você tem informações sobre os pacotes mais recentes. Se você ainda não conseguir instalá-lo depois de executar o apt-get update, então é possível que você não tenha este repo habilitado em seu servidor.
Você pode verificar se este repositório está ativado executando o seguinte comando em um terminal:
cat /etc/apt/sources.list | grep universe
A saída deste comando deve ser algo como isto:
deb http://mirrors.linode.com/ubuntu/ precise universe
deb-src http://mirrors.linode.com/ubuntu/ precise universe
deb http://mirrors.linode.com/ubuntu/ precise-updates universe
deb-src http://mirrors.linode.com/ubuntu/ precise-updates universe
deb http://mirrors.linode.com/ubuntu/ precise-backports main restricted universe multiverse
deb-src http://mirrors.linode.com/ubuntu/ precise-backports main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu precise-security universe
deb-src http://security.ubuntu.com/ubuntu precise-security universe
Se não obter saída, adicione as seguintes linhas ao /etc/apt/sources.list
deb http://us.archive.ubuntu.com/ubuntu/ precise universe
deb-src http://us.archive.ubuntu.com/ubuntu/ precise universe
deb http://us.archive.ubuntu.com/ubuntu/ precise-updates universe
deb-src http://us.archive.ubuntu.com/ubuntu/ precise-updates universe
Se a saída for comentada com # , remova os comentários do /etc/apt/sources.list
Em seguida, você poderá executar apt-get update e, em seguida, apt-get install python-guestfs
[1] link