I think an error like yours, seen when you try to Start a Geoprocessing Service either manually or as part of Add New Service (i.e. when it is first created), is likely to be due to trying to start too many Geoprocessing Services for the resources the hardware hosting them has available.
If you Stop one or two others then you should be able to Start this one.
If you do have too many Geoprocessing Services running for your resources, and are publishing each task from a different map, then perhaps try adding multiple tool layers to just one map before you publish it as a Geoprocessing Service with multiple tasks available.
UPDATE
Just realized that you are publishing a toolbox rather than a map with tool layers so much of what I said above may not apply. However, if this toolbox does not publish then maybe a smaller one with less tools might? If that's the case it would still point at system resources being limiting.
UPDATE 2
It seems like the error message I looked up and "matched" to this question is not quite the same.
Configuration ****/****_****.GPServer can not be started.
Configuration ****/****_****.GPServerJobScheduler can not be started.
Server Object instance creation failed on machine ****.
Error: 0x80080005 (Server execution failed)
I now think that attention should be paid to the "Invalid parameter" part of the Question's error message. I think you should double-check that the tool can be run from ArcGIS Desktop on the server where you are trying to run it as a GPservice. I would expect that would throw a similar error and enable you to focus on debugging the model and dialog rather than the service.
