Você não executou sudo apt-get update
por um tempo (ou usou ferramentas que implicitamente fazem isso). Agora a versão antiga do pacote foi substituída por uma nova, mas o seu sistema ainda não sabe disso. Então, sudo apt-get update
é tudo o que é necessário.