ssh server closes connection when client using NAT but work perfectly when client on same network

ssh server closes connection when client using NAT but work perfectly when
client on same network

Server: RH (though I am not sure which version) Client: Linux Mint 15
I'm trying to ssh from a machine behind a router to a server on the
network to which the router is connected. I'm using public key
authentication. I get this error:
debug1: Next authentication method: publickey debug1: Offering DSA public
key: /home/XXXXX/.ssh/id_dsa Connection closed by XXX.XXX.XXX.XXX
If I connect the client to the same network the router and server are
attached, then everything seems to work fine.
Does SSHD contact the client and could the router be blocking this
transaction? The logs are not providing a lot of information, and I do not
have admin permission for the server, so I cannot look at all the
configuration the way it is set up.