I'm seeing this same error on Windows 2008 R2 x64 when connecting to SQL Server 2008R2. The part that concerns me is that I can go through the process of adding the database to the data store via ArcCatalog, and the sde connection is added. I can also verify the connection from ArcCatalog. When I log into Server Manager, I can see the entry in the data store, but it shows as unverified. When I attempt to verify in SM, I get the red exclaimation mark. I do have ArcGIS for Desktop and ArcGIS for Server running on the same machine. Perhaps this indicates that the 32bit client is found, but the 64bit SQL Server client is not installed (correctly)? I'm guessing that even though the data store entry validates ok in Catalog, it's not really valid, as show in the SM?