This is also and issue when using the [AT+CUSD=1,"?"] command (you often get the "+CUSD: Encoding Error" error message).

For me, the fix appears to be doing:

AT+CSCS="UCS2"

delay(10);

AT+CSCS="GSM"

which appears to correctly/reliably set the SIM800 into "GSM" mode.