I can't add a new Apple ID to my iPhone after my previous one was locked

I'm doing a lot of inferring here because you do not provide much detail. I suspect you are trying to now trying to log into an iPhone with your new account, but it is requiring you enter the information for the old account before you can sign in with the new one. By the way, these is an Apple Accounts / "ID", not an "iPhone account" (there is no such thing). Since that old account has been apparently permanently disabled and you are having problems with removing the Find My setting on your device, the only solution I can think of is Apple can completely reset a device if a person can provide sufficient evidence of valid ownership. Do this online at: Activation Lock support request - https://al-support.apple.com/#/additional-support Apple says, "Proof of ownership documentation is required," but does not detail what currently constitutes proof. Prior to this new online service Apple typically required the original receipt issued by Apple or an Apple Authorized Reseller and documented provenance (so typically it would be the original owner who does this, or a descendant with legal proof of ownership). This will give you access to the device but won't restore access to the account used to lock it.There is nothing that can be done to expedite an Activation Lock request.

Apple recommends you "Keep your receipt after you buy an Apple device" --> Keep your receipt after you buy an Apple device - Apple Support