LXC is returning an error when creating new unprivileged containers

I had the same problem with Debian 9 and this thread was always on top of duckduckgo results, so I do appology for giving a solution about a Debian problem on askubuntu but it may help Ubuntu users as well :

After having installed LXC (apt install lxc) just check the result of this command :

# cat /proc/sys/kernel/unprivileged_userns_clone

If it's 0, then you may need to do this :

# echo "kernel.unprivileged_userns_clone=1" > /etc/sysctl.d/80-lxc-userns.conf
# sysctl --system

I saw this "trick" on the LXC page of Debian wiki and it worked for me.

Note: If it doesn't solve the problem for you, just remove /etc/sysctl.d/80-lxc-userns.conf and run sysctl --system again to cancel this change.

The reason why it wasn't working turned out to be the kernel which was supplied with the Ubuntu build installed by the hosting provider (SoYouStart/OVH). This kernel has less features enabled, including the ones required by LXC. I had installed a Generic Linux kernel, but not correctly updated grub and enabled it.

After following the steps for selecting the generic kernel and updating grub and rebooting, LXC worked as expected. I hope that helps someone in a similar situation.