The first thing to do is understanding which ASCII codes are produced by a certain key using the C one-liner.
Once you know which sequences are produced, you must check the current terminfo entry with infocmp (don't be scared by the amount of information printed!) and be sure that the kbs and kdch1 capabilities correspond to the right sequences (that is, the one produced by the respective keys). Moreover, you must check with stty -a that the erase character is the one emitted by the Backspace key (note that ^H represent BS whereas ^? represents DEL).
If there is a mismatch, there can be several different reason: wrong content of the TERM variable, wrong entry of the terminal database, wrong terminal emulation under X. I hope at this point you have enough information to dig the solution autonomously.
Note: If different applications behave in different ways, it is likely that some of them are using the terminal database correctly, and some are not. Remember that the fact that the keys produce the right behaviour in a certain application does not mean that the application is using correctly the terminal database—they could work just by chance. If you want to have an independent check, you can try whether the ne editor works. ne uses all terminal capabilities, including kbs and kdch1, and uses intended meaning only as a last resource.