We finally installed an instance of ArcSDE 10 today.  My first attempt at connecting in ArcCatalog 9.3.1 failed with the following error:

Failed to connect to the specified server.

This release of the GeoDatabase is either invalid or out of date. [Please run the

ArcSDE setup utility using the -o install option.]

DBMS table not found [sde.sde.GDB_Release]

 

Turns out the solution was simple, this article points out that Service pack 2 is required.  After updating my ArcGIS, the problem was solved:

I was the proud, new recipient of a non-misleading error message.  After some minor head-slapping, I realized that 9.3.1 and older versions of ArcGIS are not able to connect to ArcSDE 10.  Doh!  My bad–I should have read ESRI’s clear information on this topic.  At least I never actually tried to install ArcSDE with the -o option as the first error message instructed me to do.