It´s a bit difficult help you whitout see a bit the code, but something you have wrong. I´m sure, I use Palm Pre for all testing, it´s very low category than galaxy, and my game have a lot of graphics, 3d textures at 1024x1024, ligth, sounds and physcis all combined and my game runs perfectly at 45 FPS, of course not are 60FPS, but 2D games not have too much problem in any game, and you are using boxcolls...
Perhaps this it´s obvious but, see if you are loading some image in the bucle, when you load in example a little image, like a jpg whit 60Kb, the game turn very very Slow... I told you because when I beggin whit glbasic sometimes occurs to me...