Before you continue reading about the reasons, please be sure to activate PSN's option "Late execution" in options section "General" and try if this fixes your issue.
It is very likely that this happens when another plugin is saving posts, especially when it is a frontend post submission plugin. Some of them update a new post several times in the submission process to add categories, tags and / or custom fields. Every update triggers the WordPress internal action "transition_post_status" (http://codex.wordpress.org/Post_Status_Transitions). PSN relies on this action and every time it occurs, it will match the notification against the post update. In most cases it is not necessary to update a post multiple time in one request. It is just lazyness of the developer who is not aware of the side effects. Everything can and should be handled with one post update. So please contact the developer of that plugin you use and ask him/her to change the behaviour of post creation / updates to just update a post once per request and unique post statuses.
If that is not possible or you need a faster solution, please try PSN's "Limitations" feature if you haven’t already. It tries to log all rule matches and if you set the limit to 1, the rule will only trigger once. Well, in most cases. Some frontend plugins work with asynchronous AJAX requests and fire multiple requests at the same time which can not be handled correctly.
Another explaination can be that your rule is not exact enough. Example: Your rule matches status before "anything" and status after "anything", which can be called an imprecise configuration. If a post gets updated multiple times in one request, e.g. from "new" to "draft", from "draft" to "pending" and finally from "pending" to "publish", that rule would match every transition. In this case, if you just want to notify the "publish" event, you have to adjust the rule to be more precise, e.g. to match status before "pending" and status after "publish". To get to know which statuses a post is running through, you should create a "Debug rule" and check the logs.
If this happens with user submitted posts, we recommend to switch to the plugin Frontend Publishing Pro which does not trigger multiple posts transitions in one request and therefore works great with PSN.