It all comes down to a bug essentially where you are running an older kernel that doesn't support the newer Debian templates. The solution is to update your OpenVZ kernel.
Here are some symptoms of the problem/lack of kernel support:
Ubuntu Template 12.04 requires a manual network start:
service networking start
sshd will not start:
/usr/sbin/sshd
PRNG is not seeded
mknod /dev/random c 1 8........