Eu tive o mesmo problema. Você está instalando o pacote através do postgres repos oficial por acaso? Se sim, certifique-se de que o seu Ubuntu Codename está configurado corretamente no arquivo apt para corresponder ao repositório a ser usado.
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 15.10
Release: 15.10
Codename: wily
$ cat /etc/apt/sources.list.d/pgdg.list
deb http://apt.postgresql.org/pub/repos/apt/ wily-pgdg main
O meu foi definido como precise-pgdg no arquivo apt em vez de wily-pgdg .
Se eu estiver correto este problema surge por causa de uma biblioteca necessária deve ser compilada usando o mesmo compilador usado para o PgAdmin. Como a versão do compilador usado é diferente para precise e wily os pacotes não são intercambiáveis no caso do PgAdmin.