I'm getting a nearly identical error with AGS 10 but the .NET version on Windows Server 2008 R2. I've just installed AGS10 with a Standard Workgroup license and created a service in Manager. I can preview the service in Manager and browse to the REST catalog at http://servername/ArcGIS/rest/services/, where I can see my service name. But if I click the service link 'Ags10Test (MapServer)' in the catalog then it redirects to http://servername/ArcGIS/rest/services/Ags10Test/MapServer with the message 'Service 'Ags10Test' of type 'MapServer' does not exist or is inaccessible.'
I can browse to the SOAP service at http://servername/ArcGIS/services/Ags10Test/MapServer?wsdl fine: I get the WSDL as expected.
I'm also not able to log into the REST Admin even though my user name is part of the agsadmin group, so I can't clear the REST cache either. I suspect that if I can clear the REST cache then I might be good to go.
I'm using IIS 7.5 on the GIS server, and it has 'Anonymous Auth' enabled for the ArcGIS\rest virtual directory.
I turned GIS Server logging to verbose but nothing is getting logged either there or in the IIS logs that's of any use.