Você deve tentar atualizar seu cache do APT antes:
sudo apt-get update
Em seguida, tente novamente sudo apt-get install texlive-full
A propósito, você pode listar todos os pacotes disponíveis do texlive fazendo:
apt-cache search --names-only texlive