In order to add compatibility with SUPEE-9767, please follow below instructions.

Please do not make modifications directly on live site, test out on test site first. You can install the SUPEE 9767 patch first and One Step Checkout will continue working without issues but formkey check is not performed.

You can then upgrade the whole package to 4.5.8 (includes formkey check)

or

keep the current package and apply gist patch from Gist diff: https://gist.github.com/madismanni/72e17326cb4829a949a5dfaf26a3484a/revisions

* If you are using PayPal Plus [ Pay Pal Plus, PayPalPlus ] PayPal Plus overrides checkout.phtml, and if you are getting the error message, you need to make the modification described in above gist to the following file, app/design/frontend/base/default/template/paypalplus/onestepcheckout/checkout.phtml -------------------------

There is a check built into One Step Checkout in case form key check fails. If it fails, a message is displayed in frontend,

Please contact support@onestepcheckout.com. form_key check was not successful. SUPEE9767 validation failed.

There can be TWO causes/solutions for the issue:

I) If the issue occurs occasionally, then you are experiencing a timeout issue. The visitor's session expired. The form key is tied to the session. When they submit the form, Magento sees they have no valid session, and so creates a new one (along with a new form key). That new key doesn't match the one submitted, so they get an error--but submitting again immediately after that failure would indeed work. Solution? Raise your session lifetime.This same issue is happening on your site in all places where form key check is performed, also in Admin login, standard checkout, etc... Just it fails silently, not an error message. This silent failing seems to be PHP world and Magento standard and is a horrible habit... What you can do is increase timeout values for your site or you can alternatively hide the error message, or rename it into something else. I hope you agree error is better than silent fail, now you have an indicator that something is not optimal and can take action instead of ... silent confusion and no indicator where to look for issue ;)

Make sure cookies are staying around (I would recommend expiration date of a day or more). See: System > Configuration > Web > Session Cookie Management > Cookie Lifetime

Make sure PHP isn't cleaning out sessions prematurely. That means increasing the value of PHP setting session.gc_maxlifetime (by default, set to 24 minutes). You may have to contact your host to arrange this.

II) If you are getting the above message every time, please go through the following checklist, normally you would be getting this error after upgrade.

* Are template/skin/layout files from latest version really being used ?
Old files may be used from theme folder.
* If you are using "Combine JS into same file",
please disable that for checking from what theme folder the files get loaded and
update files if files from old package are used
* Some cache may need to been flushed. If you are using APC/XCache/OPCache, check if new files are really used
* If the above does not help, please check what checkout.phtml gets used,
there may be a 3rd party module that is overriding it.
In this case please write back to me and Form key field needs to b