Interesting. I get the same:

$ sudo apt-get install lxc

...

$ lxc

The program 'lxc' is currently not installed. You can install it by typing:

sudo apt-get install lxc

$

If you run:

$ dpkg-query -L lxc

you can see what files lxc has installed. There are a bunch in /usr/bin that start lxc-, like /usr/bin/lxc-list which do work, and some start up stuff in /etc/init.d/.

So, I reckon it is installed OK, you just need to find the name of the right executable.