Kirk - I think Linda's argument will be sufficient. A health FSA is a self funded health plan (i.e., it's subject to IRC Section 105(h)). Other than that, it isn't different than any other type of health coverage. While it's true in most cases the maximum equals the premiums, that's not always the case.
For example, suppose the coverage is $1,200 per year. An employee who incurs $1,200 of expenses in January is entitled to a reimbursement of $1,200. That employee might only be working on a prevailing wage contract for January. Or the employee could just quit in February. The employer has assumed the risk. Of course the employee has a risk of loss if the employee is in the plan for the full year and doesn't incur expenses up to the maximum. But, based on the net cost to the employer for the year, it's possible that a higher "premium" could be charged if the employer wanted to do so. If the plan were funded, the rules under IRC Sections 419 and 419A permit a higher premium to be charged. Just because the employer doesn't charge a higher premium shouldn't be a factor.
Also, you could point out that the health FSA is no different than a typical indemnity policy when it comes to utilization (the use it or loose it issue). Providing health coverage through an insurance contract in order to satisfy the prevailing wage is acceptable to the DOL. What if the employee doesn't ever use the coverage? (maybe the employee has no medical expenses, a spouse has primary coverage, or like somone at our firm, an employee is still entitled to medical coverage through the government because he is a veteran). It's no different than the health FSA. An employer is providing coverage - whether an employee uses that coverage is irrelevant.
I haven't actually had this issue raised before. We have prepared numerous qualified plans that are designed to satisfy the prevailing wage laws (such as the Davis-Bacon Act), but all of them have provided for full vesting of the prevailing wage contribution.