The Solution:

Issue solved.   The problem was, that we stepped through the code and because of that too much time elapsed between connect and authentication.  As we ran the program without breakpoints it worked.

The Problem:

The AuthenticatePw method failed and the LastErrorText contained this information:

ChilkatLog:
   AuthenticatePw:
     DllDate: Jan 31 2010
     UnlockPrefix: ***
     Username: ***
     Component: .NET 2.0
     SshVersion: SSH-2.0-XFB.Gateway Windows
     SftpVersion: 0
     login: ***
     sendMessage:
       msgName: SERVICE_REQUEST
       unpaddedLength: 22
       remainder: 6
       paddingLen: 10
       totalSize: 32
     SentServiceReq: ssh-userauth
     numBytesRequested: 16
     Connection closed by server.
     Failed to read data on SSH connection.
     Failed to read packet from SSH server.
     Error reading service accept.
     Socket connection lost.
     Failed.