How do I avoid the error "Unable to validate the following destination configurations" when using S3 event notifications in CloudFormation?

There is a very important post about avoiding the "Unable to validate the following destination configurations" in AWS.
Too bad it's not mentioned just next to both S3 and SNS/SQS reference documentation.

BUT! This post is lacking some important part: You will get this error even if you didn't specify the TopicPolicy (or QueuePolicy) at all!
Furthermore, you will get this error even if you specified the policy, but it's not correct.
For example, if your policy is too restrictive and S3 would not be able to send events to SNS, you will also get this error! Is it clear from error's description? Not really. Is it clear from the above's AWS post? No, not at all.

So just remember, when you see "Unable to validate the following destination configurations" - check the Policy. It may be lacking. It may be too permissive or too restrictive, but the problem is with the policy, and not with a bucket.