I have a 8 core processor overclocked to 4.5GHz and 16gb of 1.6GHz memory and my server still isn't running very good. With 3 people on it can't handle replacing some 2 million blocks, which might sound like a lot, but you would think with this hardware it would be able to. Does bukkit make use of all available cores? Is Minecraft thread per client? If it is, do you think Mojang will ever change that?
Two million blocks is a lot even for a serve with the specs that your's has. Just some thoughts but it could be your internet speed. Internet speed plays a very large part in the efficiency in a bukkit server.
My point is that it shouldn't be a lot, it's known that Minecraft isn't very efficient, I'm just wondering why no one has fixed it yet. My internet speeds are 20mb/s upload and 60mb/s download iirc
I did a 7 million block //set 0 last year with a 2.8GHz dual core and it handled it just fine, with only a few seconds of freezing. By any chance, are you using a AMD cpu? They seem to have performance issues with Minecraft from my experience.