I haven't been able to reproduce the behavior you described. (Double-clicking through nautilus and running from the terminal both work for me.)
To debug this, perhaps make a second script called test2.py:
[PHP]#!/usr/bin/env python import os print os.getcwd() raw_input()[/PHP]
Move the file to ~/Desktop/test2.py.
Double-click it. Does it print /home/user/Desktop ? That is what I'm getting.
If you are not getting "/home/user/Desktop", then I suspect the problem lies in some nautilus configuration option. Unfortunately, I don't know much about nautilus configuration.
If you see "/home/user/Desktop" but still get the error message when you double-click test.py, then I'm really flummoxed.
Whatever it prints is the current working directory. It is the directory that python should be searching for Instructions.pdf.
Finally, you may consider this an unsavory hack, but... if you know where the script is going to be installed, you can set the current working directory like this: [PHP] os.chdir(os.path.join(os.path.expanduser('~'),'Desktop'))[/PHP]