Attached is a proposed patch.
Some explanation behind the patch that stems from the above comments:
The following is an example of Formatter.format() returning str in the current implementation that would break if we made Formatter.format() return unicode whenever format_string is unicode:
>>> f.format(u"{0}", "\xc3\xa9") # UTF-8 encoded "e-acute".
'\xc3\xa9'
(It would break with a UnicodeDecodeError because 'ascii' is the default encoding.)
Since we can't change Formatter.format(format_string) to return unicode whenever format_string is unicode without breaking existing code, I believe the best we can do is to document the departure from PEP 3101. Since the caller has to handle return values of type str anyways, I don't think it helps to ensure that more return values are unicode.