Encontrou a solução. Algum tempo atrás, tentando fazer com que bash-completion funcionasse também para sudo , adicionei:
complete -cf sudo
para o meu .bashrc . Comentá-lo faz com que meu sudo apt-get autocomplete seja correto.