No Debian 8, nano inclui /bin/nano e /usr/bin/nano (o último é um link simbólico para o primeiro). No Debian 9, /usr/bin/nano não está mais incluído (veja #767929 para detalhes).
Presumivelmente você atualizou do Debian 8 para uma versão do pacote incluindo a correção acima. Seu shell lembrou que nano estava em /usr/bin/nano , mas após o upgrade não era mais o caso. Executar hash -r no seu shell iria corrigir isso, assim como iniciar um novo shell.