I am also encountering this issue. As someone mentioned, it appears to be some sort of local caching issue for the Desktop App. Exiting the New Teams and Opening it again or rebooting does not clear it. I had to go into Settings->Apps->Installed Apps->Microsoft Teams->...->Advanced Options and select Reset (Repair did not work).
This was fine for me, but I really do not want to walk everyone else on the Team through this process (or everyone else that had a Channel deleted on a Team).
I would like Microsoft to comment on this. I wish I had seen this before the M365 Conference last week. I would have tracked someone down. I may still try to do so. This may be an issue that has not received enough notice from Microsoft management. (I'll try anything)