The problem looks like the program is outputting accented characters in one character set, but your terminal is set to use a different character set and so you get weird output. The locale settings can include a specific character set request, although applications may or may not support the requested settings.
In Putty's configuration, please check what character set is being used. This can be found under the Window / Translation area in the configuration window. What do you have for the "Character set translation on received data" drop down listbox?
Also, when you enter the command "locale" (after logging in) what output do you get?