Hi Dan,
As Vince mentioned there are many causes for this type of error to be thrown. more information on your current configuration and what has been completed prior to this error will greatly help others in providing concrete suggestions.
> Has the geodatabase been upgraded recently?
> 'sdemon -o start' output?
> ArcSDE version? Is this a new service?
> Can you create a new service?
> Oracle, SQL Server, etc.
> Can you make direct-connections to the same geodatabase?
...