My CO issued a Stop Work Order on a FFP (services-oriented) contract for a period of about 2 months. When they lifted the Stop Work, the USG approached us regarding a downward adjustment for the "missed" time providing support to the customer since we were under the stop work.

Can the USG do that?

We encountered additional costs as a result of the Stop Work so we thought if anything there would be an UPWARD adjustment, not downward.

A stop work order stops work, it does not delete work. If they are saying that they deleted work, then they partially terminated the contract and must proceed under the Termination for Convenience clause, not the Stop Work clause. In that case, any cost increase caused by the stop work order is to be include in the termination settlement.

All of this should be clear from the language of the Stop Work clause itself.