I spent three years detailing for dealerships, and if there's any one thing I learned to be universal to all makes and models it is that you can't shampoo the headliner. It will get the stain out, sure, but all headliners are just fabric wrapped and glued to a cardboard backing in the shape of the roof. The heat from the shampooer dissolves the glue and the pressure pretty much turns the cardboard to mush. If they can't clean it with something like XtraDuty or Simple Green then they should replace it for you. Even if they can clean it, they will probably end up tearing the crap out of the fabric anyways.
Deuce