When I had problems getting the Publishing Tools service to start, I stopped and started the Windows service ArcGIS Server (formerly known as the SOM/SOC in version 10.0). Stopping the service stops the GIS server on the machine and shuts down any running GIS service instances. When the service starts up, it choose a port(s) from the correct range. I believe ArcGIS Server became corrupted during a failed attempt to publish a regular map service from ArcMap directly. It has only happened one another time since then (also publishing from ArcMap but with a different map document), and restarting the Windows service ArcGIS Server worked for me.