Bukkit

Updated with a few new well generators, including some from Khyperia

Like CityWorld, this plugin really "tests" MineCraft/Bukkit when it comes to complex worlds. In fact when you spawn/teleport into the world for the firsttime (or some wildly new location) it takes a while for all of the blocks to generate. This is especially obvious if you are flying around. Once the blocks are generated though everything works just fine. What I recommend is take a tour of your world and just walk/fly up to each "uninitialized chunk" until everything shows up.