Most government organizations (in the US) already have a stigma of hiring people who are mostly nicely described as "less than performant". If you were unable to perform to the lowest standards (a perception), there very likely is no explanation suitable enough.
If you've found that this is the case where your capabilities are dismissed without regard to actual ability simply based on the fact that you were fired from a position that is generally thought in the realm of "how on earth do you get fired from there", then your only recourse is to find some way to rebuild the reputation.
One method is to take the jobs that you feel are "beneath" you or that under pay you. Use that job to re-establish your perceived competence and capability. Regardless of industry, reputation is often everything. While it won't usually get you a job you're unqualified for, it can certainly get you eliminated from a job you are.
If you can't take a job that under pays, then you'll need to find a job with a company that isn't privy to or predujiced against this mark in your reputation. This is often a company that is out of town or one that is constantly at odds with the organization you are exiting.
If those two options aren't acceptable then heading to another city may be your only recourse. It is often easier to start from a position of "no reputation" than a position of "bad reputation".