With help from @DLynch we narrowed this down to a missing apparmor:

kemayo@visualeditor-test3:/srv/mediawiki-vagrant$ sudo lxc-start --name mediawiki-vagrant_default_1576514393929_92435 -F
lxc-start: mediawiki-vagrant_default_1576514393929_92435: lsm/apparmor.c: apparmor_prepare: 974 Cannot use generated profile: apparmor_parser not available
        lxc-start: mediawiki-vagrant_default_1576514393929_92435: start.c: lxc_init: 899 Failed to initialize LSM

Installing it with sudo apt install apparmor fixed the issue for us.

I also verified that a working vagrant VPS set up on the debian-10.0-buster (deprecated 2019-12-15) image does have apparmor installed. I can't say whether that's the image or some puppet change to the role::labs::mediawiki_vagrant role that has occurred in the last few weeks.

Oh, and on the debian-10.0-buster (deprecated 2019-12-15) image, apparmor is installed as apparmor/stable,now 2.13.2-10 amd64 [installed,automatic]. Automatic implies it was pulled in as a dependency, I think, so perhaps some part of debian (lxc?) stopped explicitly depending on apparmor in the last few weeks?

Change 558136 had a related patch set uploaded (by BryanDavis; owner: Bryan Davis):
[operations/puppet@production] cloud: add ::apparmor dependency to ::lxc for Buster

https://gerrit.wikimedia.org/r/558136

Mentioned in SAL (#wikimedia-cloud) [2019-12-16T20:16:17Z] <bd808> Building instance mwv-t240875 to test proposed fix for T240875

In T240875#5745821, @Stashbot wrote:

Mentioned in SAL (#wikimedia-cloud) [2019-12-16T20:16:17Z] <bd808> Building instance mwv-t240875 to test proposed fix for T240875

I built this instance, switched it to the project local puppetmaster, and applied role::labs::mediawiki_vagrant. Running vagrant up before applying my proposed patch on the Puppetmaster resulted in the lxc-start failure reported in this bug. Then I cherry-picked https://gerrit.wikimedia.org/r/558136 to the project puppetmaster, forced a puppet run on mwv-t240875, and finally ran vagrant up again. This time the LXC container started as expected.

Change 558136 merged by Jhedden:
[operations/puppet@production] cloud: add ::apparmor dependency to ::profile::wmcs::mediawiki_vagrant

https://gerrit.wikimedia.org/r/558136