Allow error messages with non-ascii characters to be handled correctly

Also, add a test for this behavior.
Convert many byte strings to unicode; change string formatting
Fix some line lengths to make pylint happy
Fix formatting of docstrings; add more docstrings