Im struggling with opengl too at the moment (see my glColor4f issue thread

), but i managed to get 60 fps with my tilemap finally.
I made one big vertexgrid holding 6 vertices for each quad (2 triangles), with width/height for this.
This vertex grid is textured and is drawn strip-wise.
mapHeight (actually 32x32 on 480x320 = 10 Strips) = -> 10 glDrawArrays calls and using gltranslatef for the scrolling.
Using vertexbufferobjects, if the device supports it, this is an HUGE benefit for this static maps.
This works pretty well, and this is not optimized at all, im using floating points, im using no indices, no triangle_strips. so there is a lot of optimization that can be done there, but im at 60 fps with 2 layers (so 20 glDrawArrays with alpha)
with ~40 enemies on the screen (using the drawtex extension for the enemies) i'm at ~50 fps (G1 device).
Actually i don't know the performance on an milestone or droid with bigger resolutions and other graphics chips, but this as i mentioned, there is a lot of optimization that can be done for this.
I think it would be more problematic if you would like to add animated water or something else.
I dont recommend the C-way, for 2 reasons:
reason 1: writing java code is faster development. Yeah C is waaay faster, but you can write easily the main code in java and go to C for the heavy duty functions, after you examined them with traceview or your own profiler. But thats your choice anyway (it is the fastest way you can go)
reason 2: android 2.2 comes with an JIT-compiler, this will speed up java up to 4-5 times. And then writing native code for 2d games is not more nessesary. (of course, not all devices will get the update, but i hope that the majority of the devices will get this update at some time)