JP characters are represented by two subsequent bytes. The first byte is >0x7F and the second byte can be anything. In the particular bug example, the THF character is (0x94, 0x92), and the WHM character is (0x8B, 0xE1). However, the character for Afternoon is (0x92, 0x8B). So if you put THF and WHM next to each other, the only way to tell that Afternoon isn't actually there is to respect double-width character boundaries, which gsub doesn't do for totally legitimate reasons.
So I had to write a function that would read from left to right and iterate by 2s (and 6s) when appropriate. It's probably imperfect, hence my disclaimer above, but it seems to work for all the JP shouts I've seen tonight.