After doing some searching it seems that the byte string is being encoded into (most likely) UTF-8, can only handle values up to 128 for a single byte.
From Python 2.7.9 docs:
UTF-8 uses the following rules:
1) If the code point is <128, it’s represented by the corresponding byte value.
2) If the code point is between 128 and 0x7ff, it’s turned into two byte values between 128 and 255.
3) Code points >0x7ff are turned into three- or four-byte sequences, where each byte of the sequence is between 128 and 255.
Does anyone know of a way to get around this? Maybe a different encoding? Admittedly I don’t know much about string encoding or REST.