^^ What DVader Said, plus;
(general tips - which you may already use)
look at things that don't need to be done every loop and limit to essentials such as timing and touch input - which can be annoying when it skips.
Get the system to look after things like sprite animation as it can do it much faster than your code can and so is less of a hit on performance.
Tailor your graphics to a lower Spec - lower res. devices generally have less power to downscale high res graphics, whereas high res devices generally have more power so upscaling will be less of a hit.
Lower graphic detail can be overcome by creating the graphics in much higher res. and getting an art package to scale it down with anti-aliasing, filtering and such - this creates the illusions that graphics are higher res than they are.
Limit how much you actually change regularly - only move stuff if it needs moving - look at using "dirty" flags to identify when things need to change rather than assuming they do unless checked otherwise.
Don't try to get maximum frame rates - high frame rates do not make a fast game, they do mean the game has less time to update between sync calls.
Plot the frame rate on a graph rather than just a value on screen - this will show performance over time and can identify where the slowdown is happening.
And finally - ALWAYS use timer based movement - then when slowdown does occur, the movement will compensate and minimise the impact on the user.
