I've been working on this map generator for a couple weeks now. It makes a random map built out of hundreds of little planets (see images below to get the idea). You can optionally set it to have either water or open sky at the bottom. The map with water is only half as tall, as the MineCraft engine seems to be much more resource-intense for full-height open maps.
I'm really interested in feedback / suggestions, particularly if you have feature requests.
Update - V1.75 now up! Changes:
1. Tweaked ore probabilities
2. Added ability to change planetoid density (the number is actually the number of times the generator can fail to find a good position to put a new planet before it gives up - higehr values will cause there to be more planets that are closer together)
3. Third option for map subtype added (try it and see)
Changes in v1.5:
1. Gravel now present
2. Planet radius controllable
Small warning: max planet radius on open sky causes Minecraft to crash for me, but you can still make much bigger planets. Let me know if you have problems.
Here are a couple of 64x64 chunk sample maps for the Mac / Linux users out there: