Sorry, but it's still not fixed in v2.5 Try drawing a 4x5 ellipse with brush size 1 pixel, then press Shift and see!
But as far as you trust gdi+, i got nothing to say. I expected you have drawn your own drawing routine. However, gdi+ may still be free of errors, and the problem may still be yours! I think the problem arises because in Paint.NET v2.5, a circle is drawn to contain the point where it's started to be drawn. That way you have to make some good calculations so that the diameter of the circle is the distance between the point you draw from and the point you draw to. Afaik, you need to have a Rectangle instance to draw an Ellipse in gdi+. If you can succesfully apply the idea of "contain the point which initiates you" to a square and check the results, it's easy to apply it to circles, too.
Thanks in advance..