How is it possible I can ssh to a machine from windows, but not my mac?

I'm at work right now and my colleagues prepared a Debian server for me and left.

Now I just found out that I can ssh into it using PuTTY from a Windows (XP) box just fine (no Linux machines here, sadly) but somehow when I'm on a mac, ssh [user@ip] doesn't accept my password.

Same with SFTP: WinSCP works just fine, command line SCP or any SFTP software like CyberDuck doesn't work at all. ("wrong username or password")

The only clue I have is that FileZilla on OSX is able to connect whenever I set it up to use a non-existant encoding. It complains about the invalid encoding and then connects just fine. Setting the encoding to UTF-8 or auto-detect just gives me authentication errors again.

ServerFault, do you have a clue how I could get this Mac to connect properly to the machine? Much appreciated.

Edit: Here's the output of ssh -v:

Angua:~ winsmith$ ssh -v web96_rootmaster@IPADDRESS
OpenSSH_5.2p1, OpenSSL 0.9.8l 5 Nov 2009
debug1: Reading configuration data /etc/ssh_config
debug1: Connecting to IPADDRESS [IPADDRESS] port 22.
debug1: Connection established.
debug1: identity file /Users/winsmith/.ssh/identity type -1
debug1: identity file /Users/winsmith/.ssh/id_rsa type -1
debug1: identity file /Users/winsmith/.ssh/id_dsa type 2
debug1: Remote protocol version 2.0, remote software version OpenSSH_5.1p1 Debian-5
debug1: match: OpenSSH_5.1p1 Debian-5 pat OpenSSH*
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_5.2
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: server->client aes128-ctr hmac-md5 none
debug1: kex: client->server aes128-ctr hmac-md5 none
debug1: SSH2_MSG_KEX_DH_GEX_REQUEST(1024<1024<8192) sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
debug1: Host 'IPADDRESS' is known and matches the RSA host key.
debug1: Found key in /Users/winsmith/.ssh/known_hosts:22
debug1: ssh_rsa_verify: signature correct
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,keyboard-interactive
debug1: Next authentication method: publickey
debug1: Trying private key: /Users/winsmith/.ssh/identity
debug1: Trying private key: /Users/winsmith/.ssh/id_rsa
debug1: read PEM private key done: type RSA
debug1: Authentications that can continue: publickey,keyboard-interactive
debug1: Offering public key: /Users/winsmith/.ssh/id_dsa
debug1: Authentications that can continue: publickey,keyboard-interactive
debug1: Next authentication method: keyboard-interactive
Password: 
debug1: Authentications that can continue: publickey,keyboard-interactive
Password: 

To be honest, I can't find any clues in this. Can anyone else?

So you can connect from the mac if you change the encoding? Does your password by any chance contain any funny characters like ones with accents?

if you type your password in a text editor on the mac, does it display like you expect it to?

Try reading the logs on the server so that you can see the reason for rejecting your connection attempt. /var/log/auth.long on debian-based systems and /var/log/security on redhat-based.

Are you sure that the server is running UTF-8 natively? Since thats what you have been trying to set?

try:

set | grep LANG

Then force filezilla/SSH to use that. Perhaps its xx_XX.ISO-8859-1?

Windows will use that encoding as default, i believe.

EDIT: I accidently put mozilla instead of filezilla