If you want your app to run on majority of cell phones out there J2ME (Java 2 Micro Edition) is currently your best bet. It may not be as feature rich as IPhone SDK or Google Android but it is probably the most ubiquitous platform for cell phones today. You can download a free WTK (Wireless Tool Kit) from java.sun.com and there are good tutorials on the same site for J2ME beginers.
One thing to remember is if you make use of any of the even a little bit fancy functionality of the cell phone through J2ME (SMS send/receive, Phone book integration or location based services) your app probably won't work on real handset outside the emulator - at least in US. All cell phone carriers here are control freaks and they have turned off all those permissions for any "not officially blessed" third party app. This is the main reason for the lack of any worthwhile mobile applications in the first place!
In theory J2ME has wide distribution, but in reality, the platform is highly fragmented.
I agree that the platform is pretty tightly locked down, and both of these issues make the platform useless for real development. If you want to write anything other than a Tetris clone, stick with an open platform.
One thing to remember is if you make use of any of the even a little bit fancy functionality of the cell phone through J2ME (SMS send/receive, Phone book integration or location based services) your app probably won't work on real handset outside the emulator - at least in US. All cell phone carriers here are control freaks and they have turned off all those permissions for any "not officially blessed" third party app. This is the main reason for the lack of any worthwhile mobile applications in the first place!