Did you ever resolve this problem? I am having the exact same issue - AGS 10.1 SP1 instance was working fine, and now all services are producing this same error that you are getting.
Ah never mind - I resolved my issue. Problem was actually with an ArcSDE server. I was using application server connections to connect to a 10.0 SDE instance, and the SDE service had stopped on that machine. Restarted the service and all is good.
I would also like to see any additional suggestions on this error as it is occurring frequently lately.
Unable to process request. Error handling service request : Cannot obtain a free instance.; nested exception is: com.esri.arcgis.discovery.ejb.ArcGISServerEJBException: java.lang.Exception: Could not initialize service 'Hydrology/Karst_Dye_Points.MapServer'.
We're also getting the "could not initialize service" error using Direct Connects. We have an SOE, but it's not running on all of the services that throw the error, and the SOE debugging/logging is disabled.