Anyone that has actually worked on multiplatform Java applications (particularly those for cellphones) will tell you what a pipe dream "Write once, run anywhere" actually is. Games and applications written for cellphones often have to be built to dozens of different configurations, despite there being standards such as MIDP and CLDC. This is partly why, as Tns pointed out, so may of these java games 'suck' on cellphones. The games can only feasibly be tested on so many phones, and often are series tested on one device to represent many from the same manufacturer. The problem with this approach is that different models, or even identical models running different firmware versions, can have wildly different behavior.
Tns, what games have you tried? Rule od thumb for mobile games is typically the same as for PCs and consoles-if it's a license (movie, celebrity) avoid it like the plague because it's probably rubbish. Stick to simpler games that were designed to be fun on a cellphone, rather than to advance a brand. Of course I have to push our stuff =D check out www.smallfrymobile.com for some lekker local stuff
Some other excellent titles- Prince of Persia, Rayman and Splinter Cell from Gameloft, Ancient Kingdoms 1 & 2 from Macrospace/Glu, Super Yum-Yum from IndiaGames.