SMS sending as gibberish

I'm not sure what causes it, but it seems like it's only when I send long messages that get broken into two texts.
I'll send a long text and it looks fine in AirDroid and on my phone, but the receiver just gets a big block of random characters.

Confirmed:
This only happens with long messages that don't fit into one text. Short texts send fine, but long ones are ALWAYS gibberish now.