O BitPim foi removido do upstream no debian.
Bug # 808105: pacote (s) removido (s) da instável
O Ubuntu 16.04 usa o ramo de testes do debian, assim, se um pacote for removido do teste debian, ele também será removido do Ubuntu.
Você precisaria voltar para o Ubuntu 14.04 ou instalar o BitPim manualmente a partir de sua página inicial.