I can't claim any credit on this one; James Rice told me about having met the author of Putty Simon Tatham in the pub. Anyway, if you want to switch the version of putty into utf-8 mode when you run it from your phone you can (simply?!) use:

echo -ne '\e%G\e[?47h\e%G\e[?47l'

I tried to work out what this means and in the end asked some chiark users who pointed me at a list of terminal escape codes which explains that ESC % G means switch to UTF-8.

For reference there is also a UTF-8 bug on sourceforge for s2putty but for me at least with the above fix mutt redraws happily.