Shift Trade edit permission is what is necessary. That permission is division aware so I would check that there is not some division config issue.
We also cap those notifications to 250 receiving individuals. On rare occurrences we have seen issues where someone has accidentally added that permission to some default role with hundreds of individuals. So another thing to check is that you don't have more than 250 people with that permission.
If nothing obvious, then I would recommend opening a support ticket.
------------------------------
Jay Langsford
VP, R&D
------------------------------