Ubuntu 12.04.3のカーネルは、3.8系のカーネルなので全部最新にしてiproute2も最新にしたらubuntu 12.04でカーネルモジュールのvxlanが動きました
sudo apt-get install bison flex gcc git iptables-dev libdb-dev make
git clone git://git.kernel.org/pub/scm/linux/kernel/git/shemminger/iproute2.git
cd iproute2