Suas fontes podem não estar atualizadas.
sudo apt-get update
ou o espelho que você está usando pode estar desatualizado, conforme mencionado em pergunta.
Estou tentando instalar o pacote abaixo no ubuntu / trusty64
apt-get install -y linux-image-extra-'uname -r'
e recebendo o seguinte erro
Err http://security.ubuntu.com/ubuntu/ trusty-security/main linux-image-extra-3.13.0-46-generic amd64 3.13.0-46.75
404 Not Found [IP: 91.189.92.201 80]
E: Failed to fetch http://security.ubuntu.com/ubuntu/pool/main/l/linux/linux-image-extra-3.13.0-46-generic_3.13.0-46.75_amd64.deb 404 Not Found [IP: 91.189.92.201 80]
Quando vou para o URL acima, vejo o arquivo relevante, mas com 77 no nome do arquivo, em vez de 75.
http://security.ubuntu.com/ubuntu/pool/main/l/linux/linux-image-extra-3.13.0-46-generic_3.13.0-46.77_amd64.deb
O que estou perdendo aqui?
Suas fontes podem não estar atualizadas.
sudo apt-get update
ou o espelho que você está usando pode estar desatualizado, conforme mencionado em pergunta.