Outras perguntas estavam perto de duplicatas, mas tinham mensagens de erro diferentes e soluções muito complicadas, por isso parecia sensato postar essa pergunta e resposta para tentar manter as coisas simples.
No meu caso, foi resolvido simplesmente executando:
sudo apt-get update
Espero que os outros achem que é tão simples assim: -)