Estranho. Aqui uso o kdevelop no Gnome e funciona perfeitamente.
Tenta dar um
apt-get update
antes e só depois o apt-get install kdevelop3
Se mesmo assim ainda não achar deve estar faltando algum reposítório na sua source.list. Procura no forum sobre o que colocar no arquivo sources.list do apt.
Uma boa dica também é que se vc não sabe o nome do pacote pode usar
apt-cache search o_que_vc_quer_procurar
É mais fácil do que sair testando nome de pacotes com apt-get install