Solução: Ao contrário do que mencionei anteriormente, a instalação do python3.5.1 não foi removida pela atualização. Ainda estava sob /usr/local/bin/python3.5 .
Rastreando o erro: escrevi algumas linhas de depuração em /usr/lib/python3.5/_sysconfigdata.py :
print("python-version", sys.version_info)
print("python-gcc-version",sys.version)
print("python-executable",sys.executable)
A saída foi diferente entre chamar /usr/bin/python3 e rhythmbox , mas o python-executable foi nos dois sentidos /usr/bin/python3
Quando pesquisei a instalação errada usando o local onde está o python3 e removido
/usr/local/bin/python3.5
Em seguida, purgei e reinstalei o python3 e executei apt install -f .
Então esse erro desapareceu.
Lembre-se: nunca instale coisas do código-fonte, se elas estiverem no repositório ou, pelo menos, remova-as antes que o gerenciador de pacotes as instale.