Same problem here, looking around the general solution was to change the stage folder to something short like: C:\temp
but did't solve my problem.
Now I deploy the service by saving the service definition and then publish it in the ArcGisServer Manager (web admin).
It's the only way to deploy a Geoprocessing tool for me right now...