The flurry of mobile games from Kev reminded me of my one and only foray into J2ME a couple of years back. I wrote a generic MIDP 1.0 'roll the ball' type game for my Siemens S55. Compared to a PC that phone is slow. Initially it dynamically retiled the screen every frame, but you could see the flicker
The solution was to cache the entire screen and just blit the current part to the screen - not normally the way to do these things. The other major annoyance is that there is no support for transparency in MIDP 1.0. To get that you have to use proprietary extensions. This is why most J2ME progs are recoded for each phone type.
I wrote this up, so you can see the source code as well as download the game over WAP. If you have a Siemens phone, it dynamically loads the proprietary siemens SMS classes to allow you to send edited game maps to your friends.