As a general guideline, when running into this ERROR 999999, it is always a good practice to run the geoprocessing tool Check Geometry and Repair Geometry.
The dissolving tool can create features with too many vertices (what we call Godzillas, since they can cause problem with your computer resources) and impact editing, rendering and geoprocessing. A new tool called Dicing has been developed to deal with Godillas in ArcGIS 10.0.
In this particular situation, you may also need to consider do you really need so many vertices to describe your geometry. You may use Simplfy Polygon or Simplify Polyline tools to get rid off the unnecessay vertices. Also for performance reasons mentioned above, you may also want to limit the number of features in a feature class.