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?