Elevated 4xx API error rates were caused by the introduction of a new feature to our service called "Notification Collapse Keys" which allows notification grouping, along with a limit of 32 characters for these keys. Up until yesterday, this feature did not exist and the parameter was being ignored. Requests with this parameter (collapse_key) containing a value larger than 32 characters have resulted in HTTP error 400.
To remediate the incident, we have immediately deployed an update which increased the limit of notification collapse keys from 32 to 100 characters. API error rates are back to normal.
An update: we have also identified an issue with APNs rejecting notifications with long collapse keys, and thus impacting iOS notification delivery resulting in error "InvalidCollapseId". We have rolled out a fix immediately, and iOS notification delivery is working as expected now.