I assuming you reformatted it using GUID Partition Map and Mac OS Extended (Journaled)? Because as you know that's all TM can use.
Does Disk Utility confirm that, or does DU just not recognize it at all?
In advance of those answers try using DU in Internet Recovery mode, which may work whereas the Catalina or Recovery Partition versions won't. Of course they should, but I have found it unable to perform certain fundamental tasks. I already complained to Apple about that so a fix may be in the works one of these years.
Next suggestion: Investigate using diskutil in Terminal. man diskutil for details. For example typing diskutil eraseDisk will return the options for that function. Although DU is supposed to be nothing more than a GUI for diskutil, certain functions (not related to your question) are not working properly in it whereas using diskutil does what I expect without complaint.
Why did this happen. All I know is that some disks from some manufacturers become stubborn and recalcitrant after formatting them one way and then you want to change it. I was convinced the thing was a brick but given enough persistent effort I have not yet found a disk I couldn't fix.
