Solved this problem in my Ubuntu box by installing Vim. I keep having this problem in every linux box I use. But I keep installing vim (over the existing vi)
The problem is, I can't get that "INSERT" sign at the bottom. The cursor is a black box and not a underscore-looking dash. When I backspace, it just goes over the text. Then when I type something new, the text starts getting replaced one by one. I hope you got it.
I'm changing the question!
:set showmode gave me the "INSERT" mode. But still, when I backspace, the cursor goes over the text and when I type, it starts getting replaced one-by-one.
Here's a video of my problem: http://www.youtube.com/watch?v=16f1nrepZsA