Why is Limited Dissolve irregular?
The method used in 2.68 only worked well for dissolving areas that were flat (in this case, vertices with co-linear edges) since it worked in a single pass, but wasn't good progressively reducing detail like in the example you show.

Committed an improved method r58879, This will be in any recent build or version 2.69.

Update:

The reason the result with 6 sides won't necessarily be equilateral hexagon is the order of dissolving vertices which have exactly the same difference in edge-angle (as with a circle) is undefined.

For this example to work the limited dissolve code would need to have checks to determine the order of dissolving vertices in the case where they have equal angles, There are a few ways this could be accomplished but I'm not convinced this is so important to support.

Such a case is fairly specific and not really the intended use of this tool, so I think its outside the scope of limited-dissolve to solve.

Though if it could be supported using the current dissolve code, I'm not totally against that either.