Você deve primeiro procurar pacotes git (o pacote git.core não existe)
apt-cache search git --names-only
Quando você pesquisa um pacote não instalado, pode executar:
sudo apt-file search git-core
Para instalá-lo, basta executar:
sudo apt-get install apt-file
No presente caso, você só precisa executar:
sudo apt-get install git
Por último, mas não menos importante, você deve executar
sudo apt-get update
como Oliver Salzburg disse.