CRJ-700 flight crew on EDLEE 4 STAR into DCA; received runway change. After making appropriate FMS changes; REVUE intersection dropped out and associated crossing restriction was not made.

Narrative

During descent into DCA flight was cleared by Washington Center to descend via ELDEE 4 ARRIVAL (ref DCA ELDEE 4 Arrival chart). During descent new ATIS indicated a runway change from landing Runway 1 to Runway 19 at DCA. Change was made to FMS by non-flying pilot and changes confirmed by flying pilot/Captain. After handoff to Potomac Approach we were queried as to whether we had been cleared to descend via the ELDEE 4 Arrival. When we replied that we had; ATC advised us that we had begun the descent below 15000 FT before reaching REVUE intersection. We had crossed DRUZZ intersection at 15000 FT when the runway change was entered into the FMS; but the REVUE intersection and it's 15000 FT crossing restriction dropped out of the flight plan. After discussing the problem; ATC told us that there was no problem this time; but that they at Potomac Approach had heard of other flight crews having the same problem on this specific arrival. Flight continued on to DCA without further incident. Suspect FMS software issue that deletes waypoints from route when arrival runway is changed combined with high workload and closely spaced waypoints contributing to flight crew not noticing missing waypoint and crossing restriction.