I have lots of ideas and never have the time to pursue them all.
Write your own e-mail client/server system. The MIDlet would be a simple form for sending messages to a server that forwards them on as e-mail messages. Include an address book and message templates.
Create location based services using some alternative to GPS. I have a few thoughts. Examine the IP address of the device to determine the region of the country. Ask the user for simple input like an interstate number and mile marker. Devise a gross estimation of location from user approximations like, "I'm 2 miles east of 805 and 3 miles south of 56." As long as the UI is fast and users only have to enter numbers, it may be usuable.
Pick any web service and make a GUI front end for it that makes input easier and parses/caches results. I frequently think of domain names I'd like to register. I might like an app that checks for TLD availablity using some on-line registrar. How about a dictionary using dictonary.com? Yellow pages from yp.yahoo.com? Flight schedules?
Specialty calculators are always an obvious choice. How about a tip calculator, currency conversion, or loan amortization?
I'm currently working on a text message/email/phonebook/bookmark application that can send messages, dial contacts, and open web pages to replace the internal native applications. Why? Because I'll add the ability to download or sync the databases with Outlook without requiring a data cable or Bluetooth. Please note that I can only do this on Sprint phones because they have MIDP extensions that allow me to dial numbers or launch the browser.
A little photo album/slide show application is always nice. Again, it should pull pictures from a server so I can upload my photos.