Do you pack your 16x16 images into a single texture, or do you have to bind and unbind a different texture every time you draw a quad?
It’s just one 16*16 texture that is rendered from one large VBO (with enough vertices to fill the screen). So, texture bound once pr. cycle, and one VBO is rendered pr. cycle using that texture. I am starting to think my phone is just … fubar 
Thanks for continuing to give tips though 
How many vertices are in the VBO? I wouldn’t think it would take that many vertices to tile across a phone’s display. They’re smaller than 800x600, right?
To make sure I’m understanding you correctly, you’re only use 1 texture and 1 VBO the entire frame (if that’s what you mean by cycle).
Yeah, you’re understanding me perfectly And yep, one frame ( I keep calling it loop cycle ). The display is indeed smaller, the phones are usually around 320 × 480 to 480 x 800. (The HTC Hero has 320x480). I stripped my entire loop down to rendering this one VBO (it currently has no update logic).
I’m more and more confident that something else is bothering my phone though, because even an entirely empty loop (all I’d do is clear the color/depth buffers) gives lousy FPS. I’m going to snag someone from work tomorrow and install it on their phone, to test this.