If you are getting this error when trying to deactivate a site template solution in the solutions gallery, then there is not a heck of a lot you can do until December. Apparently this is a known issue that is to be remedied in the December 2010 Cumulative Update. The problem occurs when you have either uploaded and activated a site template solution from another site collection or farm and you attempt to deactivate it OR when you create a template solution from a site in the current site collection and then you delete that site, prior to deactivating the template solution. As far as I know Power Shell or STSADM scripts are not going to help to force a deactivation either. The only way out is to restore the original template site. Then you should be able to deactivate the solution.
I have read some forums claiming a similiar error message which was fixed by cleaning out the site collection recycle bin. This is not a fix for this error as far as I know though. I think that those posts were reffering to an old template living in the recycle bin, causing a problem when trying to deactivate and delete a current template with the same name.
I think a good way to manage this issue, while you are waiting for the CU, is to maintain a “template site” which you only update and use to retemplate. You can restrict access to the site to adminsitrators so no one else even need know it exists. As long as you don’t delete the site, you should be able to deactivate the old solution and re-template the site as many times as you like.
One other “workaround” which may ease your frustration at seeing the old site template show up in the list of available templates every time you want to create a new site, is blocking the sandbox solution at the farm level. I haven’t tried it myself I have just had a breif read of this article and I don’t see why it wouldn’t apply to site template soltuions also: http://technet.microsoft.com/en-us/library/ff535782.aspx#section1