Changing between multiple Teams Free accounts within the app or browser
Ok, that does shed some light on the issue if you have company portal. It means your Android device was actually enrolled in your previous employer's tenant. This would make sense why it wouldn't allow you to log into another organization's account, because it is still under the previous organization tenant's policy.
Ideally, you would need to remove the device from company portal first. Then you would need to disable company portal device management after that. Without doing those steps first and simply just uninstalling the app will not help.
Since the correct order of conducting it was messed up and you couldn't log back in, you would have to reach out to your previous employer, have their IT admin user remove it from their end. Microsoft doesn't have authority to get into organization account to make such changes bypassing organization admin user. Unfortunately they would have to do it for you.