É uma questão de detalhes. Quando eu olhei para o leveldb, o pacote "-dev" não apareceu, mas quando eu procurei o lib leveldb, o pacote "libleveldb-dev" apareceu.
Se você não encontrar um pacote no synaptic, tentar instalá-lo no Terminal via apt-get
[ sudo apt-get install libleveldb-dev
] tentará encontrar o pacote das suas listas de pacotes. Embora não seja tão fácil quanto usar a pesquisa rápida do Synaptic, é uma solução alternativa.