Android textures not loading

Hello,
I have problem, I cannot solve myself. Sometimes random textures in my scene just do not load and object becomes black, or white, or gray…It happens only on android devices and only for a couple of restarts of a game. In editor everything works fine. Textures are PNG pictures not bigger than 800*600px.
Included picture shows one example of a problem. Icons in the menu should be textured with a green square texture.
Any ideas, what could cause the problem?
14817-screenshot_2013-08-27-23-18-13.jpg

I would suggest only using square textures that are 2^n on mobile. So …128, 256, 512, 1024… etc. And then checking the import setting of that texture to make sure any expected or unexpected alpha or banding occurs.