Возможно python у вас находится в другом каталоге?
Так вы узнаете, какой адрес подставляется при выполнении команды python3 script.py:
which python3
Посмотрите содержимое папки, из которой не удается запустить интерпретатор (и проверьте права на файлы, при их наличии):
ls -la /usr/bin
