alexsa@alexsa:~$ ./new.py
./new.py: строка 1: #!/usr/bin/env: Нет такого файла или каталога

Если запускать так: alexsa@alexsa:~$ python ./new.py - работает. Подскажите, что это может быть?

Первая строка скрипта должна выглядеть так

kublo
Первая строка скрипта должна выглядеть так

#!/usr/bin/env python

Так и выглядит:
#!/usr/bin/env python
# -*- coding utf-8 -*-

На что программа реагирует, как описано выше.

А если так
Может у вас не установлена утилита env ?

Может быть, а что это такое?
Кстати, у меня Ubuntu 11.04

kublo
А если так

Код:
#!/usr/bin/python

так тоже не запускается

А ошибку какую выдает ?

alex-sa
так тоже не запускается

Выхлоп сюда команд

which env
which python

kublo
А ошибку какую выдает ?

#!/usr/bin/python: Нет такого файла или каталога

cutwater
Выхлоп сюда команд

which env
which python

alexsa@alexsa:/media/Рабочий/PYTHON$ which env
/usr/bin/env
alexsa@alexsa:/media/Рабочий/PYTHON$ which python
/usr/bin/python