Thanks for the reply, Kevin. We re-authorized our server with an Advanced license and the geoprocessing service works now. I did a little digging and finally found a brochure that mentions "Advanced Geoprocessing" and license leveling. I think it would be good if this was mentioned in the help somewhere.