What version are you using? If you're at 10.1 or greater, if you look in the arcgisinput folder on the server, (C:\arcgisserver\directories\arcgissystem\arcgisinput\<service>.GPServer\extracted\v101), are all dependent files copied over correctly? If not, does the ArcGIS Server account have at least read access to wherever those dependent files are?
There are several ways you can do this without manually copying your script files to the server.
1. You can copy all the python files you wrote and saved under the same folder of the python file you are publishing. 2. You can save all the python files you wrote under the the folder where you specify the system variable PYTHONPATH. 3. You can hard-code the path of the folder that contains all the files you wrote, then use sys.path.append to append the folder in the publishing script.