My friend tested my game on a Motorola Defy (with CyanogenMod v4.x, I don't remember exact version number, and she is not reachable now).
My game uses OpenGL ES (v1.1, and in another activity, v2.0). She reported that during each "new game" start, several textures are missing, so game graphics is partially rendered only. Sometimes all textures are loaded.(Note that we release textures properly. No leak is present.)
We use power-of-two textures. The app works fine on a variety of non-CyanogenMod Android devices (including phones and tablets with Android versions between 2.2 and 4.2). That is, it worked fine on all test devices we've tested it on so far.
OpenGL ES does not return any glError, but I noticed that some texture IDs are negative (they are stored in an int in Java, so I thought this is OK). Unlike in case of standard Android devices (where texture IDs are 1,2,3,4,...), this device seems to return totally random-looking texture IDs.
So these are the details. I'm wondering why sometimes all textures appear and at other times, only some of them.