Looks like you're running your script as a CGI-script (your edit confirms that you're using CGI)
...and the initial (empty) print is required to signify the end of the headers.
Check your Apache's error log (/var/log/apache2/error.log probably) to see if it says 'Premature end of script headers' (more info here).
EDIT: a bit more explanation:
A CGI script in Apache is responsible for generating it's own HTTP response.
An HTTP response consists of a header block, an empty line, and the so-called body contents. Even though you should generate some headers, it's not mandatory to do so. However, you do need to output the empty line; Apache expects it to be there, and if it's not (or if you only output a body which can't be parsed as headers), Apache will generate an error.
That's why your first version didn't work, but your second did: adding the empty print added the required empty line that Apache was expecting.
This will also work:
#!/usr/bin/env python
print "Content-Type: text/html" # header block
print "Vary: *" # also part of the header block
print "X-Test: hello world" # this too is a header, but a made-up one
print # empty line
print "hi" # body