Encontrou a solução: Eu originalmente tinha a impressora trabalhando sob 11.10 com o michael gruz ppa, mas isso não funcionava mais em 12.04 e tentar instalar a partir do gerenciador de impressão do Ubuntu também não funcionou.
Encontrei um michael gruz ppa que foi atualizado para 12.04: link
Primeiro removi o driver antigo com o Gerenciador de Pacotes Synaptic e adicionei o novo:
sudo add-apt-repository ppa:michael-gruz/canon-trunk
sudo apt-get update
sudo apt-get install cnijfilter-mx870series
Depois de fazer isso, a instalação da impressora com o gerenciador de impressão funcionou.