Error: Common start logic:
Failed to start device "eth0":
Failed to create the veth interfaces vethec99086b and veth9a2d5cde:
Failed to run: ip link add dev vethec99086b type veth peer name veth9a2d5cde:
Error: Unknown device type.
Oh god. Apparently I updated my kernel too when I started updating lxc. Maybe this has something to do with it, not sure. After a system reboot, it works just fine now. Sorry about the fuss.
This just happened to me too, for some reason veth.ko had vanished. Apt reinstalling linux-modules-blah put it back in place. When I reboot the server veth.ko has vanished again >.<