Hi,
Is it all services or just the Geoprocessing ones?  I had an issue where none of my GP services were running, including the 3 system ones (CachingTools, PublishingTools, ReportingTools).  I installed a fresh copy of 10.1 on a machine that originally had 10.0.  The problem was a missing pointer to the Python folder (e.g. C:\Python27\ArcGISx6410.1\Lib).  Put that in your Environmental PATH variable and restart the ArcGIS Server service.  Hope that helps.
Ian