RDM, I wonder if it wouldn't be better (in email6) to use an instance to represent the 3-tuple instead?  It might make for clearer client code, and would allow you to default things you might generally not care about.  E.g.

class NonASCIIParameter: # XXX come up with better name
  def __init__(self, text, charset='utf-8', language=''):

It's unfortunate that you have to reorder the arguments from the 3-tuple form of (charset, language, text) but I think you could play games with keyword arguments to make them consistent.

In general the patch looks fine to me, though I suggest splitting test_add_header() into separate tests for each of the three conditions you're testing there.