Qual versão do Ubuntu você está executando? Eu vou assumir 12,04 para esta resposta.
Se você estiver em um VPS, pode ser que seu provedor de hospedagem tenha repositórios diferentes dos repositórios padrão do Ubuntu.
Verifique /etc/apt/sources.list
para garantir que você tenha um repositório Universe configurado, por exemplo, você tem as seguintes linhas não comentadas:
deb http://us.archive.ubuntu.com/ubuntu/ precise universe
deb-src http://us.archive.ubuntu.com/ubuntu/ precise universe
deb http://us.archive.ubuntu.com/ubuntu/ precise-updates universe
deb-src http://us.archive.ubuntu.com/ubuntu/ precise-updates universe
Também pode ser que você tenha atingido um problema de espelho inválido, rede temporária ou DNS, embora isso provavelmente acabe com sudo apt-get update
.
Depois de qualquer alteração, você precisará atualizar novamente.