Jeroen, Marco,
Densify is an Arc 10 function and that should work if you're there. In 9.3 some combination of SMOOTH and GENERALIZE will accomplish what you need to convert a parametric curve into a series of vertices.
Generalize should work for circles and ellipses, which as parametric curves are defined by only a few vertices and some code. To get the density of points that is suitable for your purpose, start with a low number like 1 or 0.1 and work up, or undo the edit and try a lower number.
What I meant about empty geometry refers to the scaling or coordinate system you are in and therefore what offset value you use with generalize. If too big a number it interprets the feature as empty.
Seems a bit odd that this is happening to your ellipses anyway since exporting a circle or ellipse in Arc9.3 automatically triggers conversion to a series of vertices that approximate the true curve. There is no direct ellipse feature drawing in 9.3 only graphic so I converted a graphic ellipse to a gdb feature which retained the parametric curve definition, then exported to shp.
Since gdb parametric-feature to vertice-defined shp conversion works without intervention in 9.3; I'd suspect you have a problem in 10 with your installation, perhaps as a result of some Windows update, which has been a suspected plague with some gdb functions for me recently.
Some added thoughts: sounds like you are exporting or copy-pasting into an existing SHP. Try instead exporting the layer to a new shapefile i.e. right click on the layer in the TOC and export data if that is how it looks in 10. There may also be a new setting in 10s version of AdvancedArcMapSettings that is too big that defines the number of vertices on export.
Hardolph