We have two ArcGIS 10.1 servers running on RedHat Enterprise Linux 6.3 that are clustered - when I access a service (from the arcgis/rest/... web page) on one server it works fine, but on the other one I get a message
Error: Error handling service request: Could not find a service with JNDI name 'service' in the configured clusters. Service may be stopped or ArcGIS Server may not be running. Code: 500
I've restarted ArcGIS on that server - no luck. This is the server that the service was published on. In the ArcGIS Manager it shows as Started.
I had a problem with my Service log on that gave a similar result. When I changed from local system account to This Account it fixed the problem. It could also be a permission issue in the file tree somewhere.