I think I'll make 0.5 free and try out AdMob to get some experience with mobile ads.
What should the main app screen look like? Tried mocking up a bit but everything looks horrible.

That list is supposed to show some popular names. Is showing the complete list of available names necessary? It's way easier to pick things from a list than try to come up with names to try without any hints. Most convenient would be if I could access their address book and show some names from there. In any case there should be a free input field in case the user wants to input something that's not in the list.
I already have an idea for the next app. I think it's an original idea, uses the platform well, is easier to make than Your Japanese Name and has wider appeal.
Update: New mockup for 0.5.

Progress is slow. Got a bit distracted and made a site for posting to Twitter using Chrome speech recognition.