We're having this issue as well, not just Android devices, happened on my iPhone5 as well, just once though.
Its really hard to reproduce this issue which makes it hard to debug...
Aren said this in another post:
When the texture's dimensions change, NGUI marks the font as dirty, which in turn forces all labels to refresh their content, which should cause everything to update correctly.
According to Unity's Doc on Font.RequestCharactersInTexture:
RequestCharactersInTexture may cause the font texture to be regenerated if it does not have space to add all the requested characters. If the font texture is regenerated it will only contain characters which have been used using Font.RequestCharactersInTexture, or using Unity's text rendering functions during the last frame. So it is advisable to always call RequestCharactersInTexture for any text on the screen you wish to render using custom font rendering functions, even if the characters are currently present in the texture, to make sure they don't get purged during texture rebuild.
So its either the font's textureRebuildCallback doesn't get called, or (some of) the labels didn't refresh their content therefore didn't force the font to call the RequestCharactersInTexture?
I'm wondering, instead of calling RequestCharacterInTexture for each labels on the screen, can we call the RequestCharacterInTexture API once and pass the combined string of all the labels? Is it even worth a try?