Tive o mesmo problema.
Tente:
sudo apt-get install qt5-default qdbus-qt5
Parece que o pacote qdbus foi dividido. Não tenho certeza se a instalação padrão do qt5 é necessária, mas funcionou para mim.
Acabei de inicializar um novo Kubuntu 13.10 ISO em uma máquina virtual e tentei executar qdbus e recebi um erro dizendo que nem uma única instalação do Qt foi encontrada:
qdbus: could not find a Qt installation of ''
O pacote qdbus está instalado. Como posso fazê-lo funcionar sem instalar qdbus-qt5 como fiz na minha máquina principal, onde ela quebrou um pouco diferente?