Edit
I tried this again, ran into problems, and discovered a package vim-nox
that already has vim support.
Original answer
I'm not entirely sure how I did this in the end, but thanks to @wrikken for the tip about headers.
# Install lua from binaries (these are out-of-date but at least they worked).
sudo apt-get install lua50 liblua50-dev liblualib50-dev
# Remove old vims
sudo apt-get remove vim vim-runtime gvim
sudo apt-get remove vim-tiny vim-common vim-gui-common
# Download and build a new vim
sudo apt-get install libncurses5-dev libgnome2-dev libgnomeui-dev \
libgtk2.0-dev libatk1.0-dev libbonoboui2-dev \
libcairo2-dev libx11-dev libxpm-dev libxt-dev python-dev ruby-dev mercurial
cd ~
hg clone https://code.google.com/p/vim/
cd vim
cd ~/vim
./configure --with-features=huge \
--enable-rubyinterp \
--enable-pythoninterp \
--with-python-config-dir=/usr/lib/python2.7-config \
--enable-perlinterp \
--enable-gui=gtk2 --enable-cscope --prefix=/usr \
--enable-luainterp \
--with-lua-prefix=/usr/local
At this point, check the output of ./configure to see that it found lua.h. If not, find out where it is (I'm afraid I can't remember where it was). Symlink to it in /usr/local with e.g. sudo ln -s ../lua.h
and rerun ./configure.
Finally:
sudo make VIMRUNTIMEDIR=/usr/share/vim/vim74
sudo make install
If it still won't work, post on a forum somewhere and go for a walk in the outdoors. You'll find it suddenly starts to behave.