Shebang executable not found because of UTF-8 BOM (Byte Order Mark)

Shebang executable not found because of UTF-8 BOM (Byte Order Mark)

For some reason the shebang in one of my scripts does not work:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
print "Hello World"
When I execute this file, I get an error
% ./test.py
./test.py: 1: #!/usr/bin/env: not found
There is no problem with the content of my /usr/bin/ directory: both env
and python are there, with correct execution rights.
I have lost some time on this problem, so I figured the solution belongs
here.