The easiest way to deal with this is to add your sender ID to the app manifest, so Parse registers with both its sender ID and yours:

https://parse.com/docs/android/guide#push-notifications-sett...

This requires a new release of your app, but that is a necessity in any case.