So I am a big fan of the vimfiles that scrooloose put up on github. I cloned them awhile back, and used them as a base for my own setup.

One of the things he does is choose a theme based on the capabilities of the terminal. As soon as I installed ubuntu 10.04, I started getting this

E558: Terminal entry not found in terminfo
'gnome-256color' not known. Available builtin terminals are:
    builtin_gui
    builtin_riscos
    builtin_amiga
    builtin_beos-ansi
    builtin_ansi
    builtin_pcansi
    builtin_win32
    builtin_vt320
    builtin_vt52
    builtin_xterm
    builtin_iris-ansi
    builtin_debug
    builtin_dumb
defaulting to 'ansi'

The issue is that terminfo is set in a non standard way in ubuntu (no idea if this is a gnome issue or an ubuntu issue). Turns out, there is a quick fix

apt-get install ncurses-term

No idea why it works (honestly, I have already spent way too much time on this), but it does. Hopefully that helps someone :-) At the least, it will save me some googling next time I run into this issue...