I was a fake vi user for a few years before I finally decided to sit down and learn it. What helped me get into the "feel" of vi was finally disabling my arrow-keys and forcing myself to use the hjkl keys for movement. It will suck for the first few weeks but eventually you'll notice a significant increase in productivity. Throw this into your .vimrc:
NetHack (or Angband, et al.) is another great way to learn hjkl. I can't say you'll notice a significant increase in productivity, but you'll at least get accustomed to the keys.
map <Left> <nop>
map! <left> <nop>
map <right> <nop>
map! <right> <nop>
map <up> <nop>
map! <up> <nop>
map <down> <nop>
map! <down> <nop>