Devido a alterações dos nomes nos pacotes do qt4 (libqt4-core é libqtcore4 e libqt4-gui é libqtgui4) no ubuntu 16.04 é preciso fazer a alteração dos nomes das dependências de modo a conseguir a instalar o pacote DEB do Cartão do Cidadão, por exemplo o ficheiro cartaodecidadao-ubuntu.amd64.deb (64 bits).
Para fazer essas alterações podem consultar http://azulebanana.com/bluey/tag/cartao-de-cidadao/ ou então fazer o download do pacote DEB já alterado a partir daqui (cartaodecidadao-ubuntu.amd64.modfied.deb - 64bits).