Can you give more details on how you were publishing this service? Also, did you click on the Analyze button before publishing the service to see about any errors prior to publishing?
It looks to me to be a permission error to your SDE database. Does the arcgis (or is it arcgissoc in 10.0?) have permissions required to you SDE database? And if so, can you test your connection to it using the credentials?
I'm betting you can connect to your SDE database just fine, but the ArcGIS server cannot. Try installing the ODBC drivers for your database on the ArcGIS Server, e.g., if using SQL, SQL Native Client whatever version.
