Several things spring to mind.
The ATC clearance to cross CEGAN at or above 7,800' implies that the crew is safe all the way down to 7,800.' It appears that ATC took the position that the procedure required 10,000 at CEGAN, and therefore a clearance to cross at or above 7,800 didn't prevent them from following the published numbers. This is a very dangerous slippery slope, and I don't buy it.
What if ATC had said "at or above 1,000?" Clearly it's not possible, but it implies that the crew may commence the procedure at the ATC altitude. ATC frequently provides vectors at altitudes lower than procedure altitudes, such as vectors to a localizer or ILS. The approach guidance with a glideslope is nearly always intercepted from below.
In this case, I'd be leary of beginning the approach at CEGAN at anything less than 10,000. That said, one might look at the arc and the high points along the arc to note that The highest point to be encounered is joining the inbound course from the arc, and that altitude is 7655. One might be forgiven for hearing the altitude restriction, glancing at the chart, and believing that based on the presented data, the clearance and arc imply guidance safe from terrain.
At the same time, neither crewmember had flown this procedure or routing before?
While the arc is beyond the 25 nm MSA radius, the radius for that area varies between 8,800 and 10,700; a crucial clue that 7,800 may be unwise, despite the potentially disasterous clearance.
Another important clue is that BRKET (27 DME OED) is published at 10,000, the next fix inbound is SERTE (21 DME OED) at 8,500. Clearly at that point in the approach one is still restricted well above 7,800, and a review of the procedure and briefing of the procedure should be enough to convince to fly the published altitudes.
Another observation is that both crewmembers heard the clearance and both agreed to the decision to descend below published altitudes, apparently. The narrative doesn't suggest one crewmember voicing an objection.
This reminds me somewhat of the B757 mishap in Colombia years ago, American 965, in which the crew was cleared via an NDB, but entered the wrong one. Both crewmembers bought into the decision, and ultimately they did get a GPWS alert prior to impact.
If this procedure was database selectable, were they not seeing the segment altitudes in more than one place; procedure charts or displays as well as on the FMS/FMC?