Engineering is all about making tradeoffs between cost, schedule, risk, and benefits. The CEV is no exception. It sounds like the standard J-2 engine isn't powerful enough to do the job with a 4-segment SRB but an upgraded J-2 along with a 5-segment SRB probably would be, especially when combined with a less massive CEV capsule. There would be some R&D associated with upgraded the J-2 but there were design studies done back in the 1960s, so they shouldn't have to start from scratch. The J-2 has a proven inflight start and restart capability, unlike the SSME, but IIRC, it wasn't throttleable like the SSME. I don't know if that will be significant but I doubt it.

NASA dropped the requirement for methane engines on the service and lunar modules but the contractors are still free to propose them in their designs. That leaves open the possibility that methane engines will still fly but the contractors will have to satisfy NASA and Congress that the engines won't result in schedule or cost pressure.

I'd like to see the proposed propellant geometry for the 5-segment SRB. From the diagrams I've seen, it appears the 4-segment SRB uses a simple hollow core through all 4 segments. This results in high initial thrust with increasing thrust levels as the burn continues and exposes more propellant surface area. However, it seems that if they go with a 5-segment hollow core, the initial pressure would perhaps be higher than the SRB casing was designed to handle. For the CEV, they might change the propellant geometry to something altogether different from what is used on the Shuttle. For example, they could go with a hollow (perhaps tapering) core through 3 segments and then have solid core for the remaining two. That would provide high initial thrust to get off the pad quickly followed by lower thrust levels during the rest of the burn (like an Estes model rocket engine). This would keep the pressures manageable and would also keep the G loads in the reasonable range as the propellant burned off. A 5-segment arrangement like that would have more than 25% more propellant than a Shuttle SRB and a longer burn time (probably on the order of 3.5-4 minutes), meaning the second stage wouldn't have as much work to do to get the CEV into orbit.