Fix an encoding issue, add a test.

PTAL @dhermes -- this seems like a good fix, though honestly i think maybe the original `str(k)` and `str(v)` works fine (from my experimenting with httplib/httplib2 in py2 and py3).