The problem is that PuTTY in UTF-8 mode ignores1 VT100 "Alternate character set" commands, and ncurses attempts to use the "graphical" character set for drawing the GUI. (The box drawing characters are in the same positions as klmqx
would normally be.)
export NCURSES_NO_UTF8_ACS=1
to your environment, it should fix the problem by telling ncurses to always use Unicode box drawing characters when a UTF-8 locale is selected.
1 There is a PuTTY wishlist entry for this, along with explanation why the current behavior is better.
Update (2018-05-12): It seems that this combination will be supported in PuTTY 0.71.