Eu tenho o GNOME Boxes instalado e rodando no Ubuntu 12.10 Quantal Quetzal (na verdade Ubuntu Gnome Remix com o GNOME3 PPA ativado).
De acordo com a barra de lançamento , você pode encontrar o pacote gnome-boxes
no universo repository que é ativado por padrão. Verifique se ainda é o caso, ressincronize os arquivos de índice de pacotes, atualize e tente instalar as caixas do GNOME novamente:
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install gnome-boxes
Se não funcionar, talvez você possa adicionar o PPA do GNOME3 e tentar instalá-lo novamente, já que parece ser a única diferença entre nossas configurações:
sudo add-apt-repository ppa:gnome3-team/gnome3
Este PPA oferece pacotes que não foram incluídos por padrão no Ubuntu. Tenha cuidado para não atualizar e removê-lo depois, se você não quiser.
Rémi.