I didn't look at your part, so I can only offer generalizations. It is a mystery to me, as well, why deleting a dimension will push a sketch from OK to over-defined. What I usually find is that various elements in the sketch are over-defined in ways that normally don't cause problems. For example, two lines are parallel and both are also perpendicular to another line. Usually these extra relations don't cause problems, but it may be that too many of them drive SolidWorks over the brink.
Sometimes the SketchXpert Diagnosis tool will find a helpful solution, although it really can take quite a while to work out a complicated sketch.