Com qmake , precisamos de libqt4-dev também, isso não foi sugerido no erro e estamos por nossa conta para descobrir, de todos os pacotes qt, o que precisamos.
sudo apt-get install qt4-qmake libqt4-dev
ou pesquise qt4-qmake e libqt4-dev no gerenciador de pacotes Synaptic e instale respectivamente.
Então eu instalei o qt4-qmake , mas também precisei instalar o libqt4-dev , o que eu não fiz.
P.S. Como sugerido em um comentário, fiz isso
apt-rdepends --build-depends --follow=DEPENDS qt4-qmake
apt-rdepends --build-depends --follow=DEPENDS libqt4-dev
a lista de qt4-qmake não mostra que precisa da libqt4-dev, nem a libqt4-dev mostra que precisa de qt4-qmake.