I agree with what hopepg posted as one of your options. Other things to consider:
After Medicare made the decision to stop accepting consults, they put out guidance that, when Medicare is secondary to a commercial payer (or any payer that still accepts consults), the provider can either 1. bill a consult code to the primary payer, then once claim is paid crosswalk the consult to an appropriate new/estab E/M code, and file that to Medicare secondary with the primary EOB. OR 2. not use the consult code at all, just file a new/estab E/M to both payers, which is easier in the long run, but you'll possibly be missing out on reimbursement from the primary payer. Depending on the primary payer's fee schedule, this may or may not be the right decision for your practice. There's a pretty fair chance that the primary payer has already paid more than Medicaid allows, no matter which code was used, so it may end up being a write off no matter which way you go.
Also, you'll need to verify with your state Medicaid office that they will allow this same "crosswalk the code after a consult has been billed to primary" thing.
I'll try to find a link to Medicare's rule so you can have it to refer to.
HTH some!