Error while trying to send push notifications

I've recently ejected expo application into the bare workflow and changed the package name. Now I can't send notifications from my own backend using expo-server-sdk or expo notifications push tool. Error I get is the following:

[
  {
    id: 'e17a1f3a-7c5b-41fe-8446-89ba6cb22027',
    status: 'error',
    message: "Unable to retrieve the FCM server key for the recipient's app. Make sure you have provided a server key as directed by the Expo FCM documentation.",
    details: { error: 'InvalidCredentials', fault: 'developer' }
  }
]
{
  'e17a1f3a-7c5b-41fe-8446-89ba6cb22027': {
    status: 'error',
    message: "Unable to retrieve the FCM server key for the recipient's app. Make sure you have provided a server key as directed by the Expo FCM documentation.",
    details: {
      fault: 'developer',
      error: 'InvalidCredentials',
      sentAt: 1597911004
    },
    __debug: {}
  }
}

I've tested with android. After old server key failed I tried creating new server key and uploading it to expo server

expo push:android:upload --api-key

Which resulted in the same error. I tried deleting the api key from expo server (expo push:android:clear) first and uploading it again, same result. Then I tried to create a new firebase project and redoing the steps as described in expo documentation only to get same results. I even waited couple of days to see if problem will resolve itself while trying to come up with ideas. My knowledge and googling have failed me so any help would be greatly appreciated. If you need further information please let me know.

Thank you in advance!