Is your username on your local box the same as it is on the ssh server? If not, then you might want to try specifying the remote username on the command line. For instance:
As far as I know, ssh defaults to the current username when it's invoked. In other words, if your username is klmbrt, it will default to logging into the remote machine as user klmbrt. Typically though, you have the chance to change it. Then again, things may be set up differently with their server.
If that doesn't work, then I'd review what settings they tell you to use in PuTTY, and see if you can match up those same values with the options ssh provides in its man page.