Ok I finally found the problem. I was setting up a few apps at the same time, so for ease I reused the certificate signing request when creating the APNS certificates for SNS. Apple and SNS didn't show any indication that there was an error with the certificates so I assumed they were fine, but all but the first one were invalid.
As the SNS error said the token was invalid I didn't think there was any issue with the certificate, but after regenerating them all with new CSRs, every thing started working fine.
The moral of the story:
Certificate Signing Requests can only be used once, reusing them won't cause any errors, but will generate invalid APNS certificates.