I feel your pain ... SFTP is a rather overloaded word (some people construe it to be FTP over ssh, some people construe it to be SCP and some explicitly SFTP). Your debug statements lend me to believe that the server is not really configured (or properly configured) for SFTP. Can you SFTP outside of perl? (does putty include an SFTP client?). Can you SCP or SSH outside of perl?
I have no experience with SFTP (or SSH) in windows, but for my *nix work, I prefer Net::SSH2 over all the other SSH/SFTP modules.