SSH Backspace Not Working? It's a terminfo Problem

You install a shiny new terminal app, everything works great locally, then you SSH into a remote server and suddenly Backspace stops working. Instead of deleting characters, it prints spaces. Here's w