Я одно время тоже столкнулся с аналогичной проблемой с кривыми utf8 строками. В итоге переделал код - декодировал строку на джава слое, передавал в нейтив, потом возвращал в джава слой некодированную строку в виде массива байт и вызывал new String(bytes, UTF-8)