Are you using some kind of bugged object in the policy?
No. That was nothing to do with a "bugged object". With the help of Fortinet support I found why I couldn't have added any additional policies between the interfaces.
We all know that firewall policies are processed from top to bottom. To achieve a desirable result you have to place any new policy in a proper place between other ones. ...and for years I used FortiOS' GUI "Insert Policy Above" and "Insert Policy Below" options to do just that. You click one of those options - it opens "Create New Policy" window for you, and then - you would simply configure all policy's properties in it and click <OK>.
But with FortiOS 5.2.3, although both "Insert Policy" options are still there, it doesn't work as expected any longer. It does actually insert a disabled policy with action DENY and nothing else configured, but you have specifically open it to do all the configuration. ...and as soon as you click <OK> - you get that above mentioned pesky message.
The "solution" was not to use "Insert Policy" options but creating a whole new policy from scratch. New policy is placed at the bottom of a section which lists all policies between a pair of interfaces - and that's bring a whole new question: Is there a simple way to reposition policies in one interface section without the need to reconfigure few of them to ensure a proper firewall's behavior. I do not see those anywhere in GUI and CLI.