Sounds like the telnet client you are using isn't sending what your Linux telnet server expects.
Try setting your client for a different type of terminal, as previously suggested. VT100 usually works well. You will probably want to closely match what your Linux server is set for. You should be able to see what TERM your server is expecting by typing "env". If the TERM variable is set, it tells you what keymap has been loaded on the linux side. Then it is a matter of setting your client software to the same thing (or a variant thereof).
If you still have problems, there are ways to map your keys. It isn't simple, but by reading the man pages you should be able to figure it out.
You may want to consider a different term program, like Tera Term. It's free, and highly configurable. It supports SSH. Also, it has a special config just for the backspace key.
Good luck!