Deve ser isso:
aptitude -F %p search '!~i'
Isso listará todos os pacotes atualmente não instalados (incluindo pacotes virtuais e pacotes que possuem apenas seus arquivos de configuração instalados). Se você não quiser pacotes virtuais (é o que o Synaptic mostra como Não instalado ), estenda o padrão de pesquisa para:
aptitude -F %p search '!~i!~v'
Provavelmente você precisa instalar o aptitude
, já que ele não faz mais parte da instalação padrão do Ubuntu 10.10.