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