Comment 8 for bug 491615

Install the full 'vim' package if you want a user-friendly vi (complete with syntax highlighting and other bells and whistles); the vim-tiny package is for basic compatibility with traditional vi, which is what many sysadmins tell us they want, and one of the things the 'compatible' option includes is disabling the 'esckeys' option. We don't have space for the full vim package in a standard installation, but anyone who can cope with vi should be able to cope with installing it quite easily.

This isn't a gnome-terminal bug either - it's fine for it to send ESC O A on cursor-up.