I think Mario is on the right track here. Is python at
/usr/bin/python? Check by running this command:
Also, check if your script runs correctly without specifying python (that's what the hash-bang line is for):
Finally, make sure that the command run by the desktop shortcut (right click => properties) is one that runs correctly from the command line.
Since it seems to be a path problem, sdd the full path and command to the desktop shortcut. Right click => Properties and edit the command. If your script is in, for example,
/home/brian/myScript.py use this as the command: