@Roy Thanks for posting in our Q&A.
Please understand that the app's package name must be globally unique in Google Play (not just unique within your enterprise or Google Play Developer account). Otherwise, you will receive the Upload a new APK file with a different package name error.
https://learn.microsoft.com/en-us/mem/intune/apps/apps-add-android-for-work#managed-google-play-private-lob-app-publishing-directly-in-the-intune-console
If you never use this "Line-of-Business" application again, it is suggested to delete the LOB app in intune portal and then upload the APK file to Google Play Store again to check if this error message still exists.
If this error still exists, it seems that the same name package file has been uploaded to Google Play by others. It is needed to change the package name as an unique name.
Hope it will clear some confusions.
If the answer is the right solution, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.