Sometimes there is the need to reinstall the Access Control policy first after major changes are made to Threat Prevention, and this will cause the TP policy installation to fail. But there is a different message to that effect when that occurs which does not match your situation.
The "Policy installation failed on the gateway" message just means that the policy was successfully transferred to the gateway, but when it attempted to actually apply it to the INSPECT engine an error occurred. Generally you will need to start a debug on the gateway and then have it try to reinstall the policy by running the fw amw fetch local command. In my experience this type of failure is caused by the following:
1) Resource shortage on the gateway, usually memory but could be disk space, this failure will tend to come and go
2) There is an error in the compiled TP policy (duplicate reference, syntax error, etc.) that should have been caught by the SMS but was not due to something bizarre in your configuration or a bug in the SMS code generation itself. The gateway will do a quick sanity check of the policy it is about to install, if it sees something wrong it will abort the policy load to INSPECT with this error. The gateway debug can help find what this issue is, I believe the needed debug flag is "policy".
3) Bug in the policy loading code on the gateway (not common).
A workaround I've seen fix this is unchecking all TP blades on the gateway, reinstalling AP/TP policies, then re-enabling the TP blades you are using one by one in the following order, with an AC/TP policy reinstall between each one, which will sometimes refresh and shake loose whatever is causing the error:
1) IPS
2) AV
3) AB
4) TX
5) TE
Gateway Performance Optimization R81.20 Course
now available at maxpowerfirewalls.com