"Unable to complete login process due to delay in login response"

Server: SQL server 2005 enterprise
Client connection: If attempted using SQLNCLI, we get the message in title after some time (no explicit connection timeout setting). The strange thing if we try connecting with SQLOLEDB instead, the connection succeeds instantly.

Because of new datatypes we need to use SQLNCLI. I have been trying this and that to no avail (except increasing timeout which doesn't make sense to me when SQLOLEDB connects instantly). Is there a solution to this. Where should I look exactly (at serverside and/or clientside).

Thanks in advance (timeout should be the last resort)