I'm testing on Ubuntu Server 16.10, with kernel 4.8.0-32-generic. In case it helps, here's an execution with bridge setup and various pieces of system information.

Script started on Fri 13 Jan 2017 11:37:55 AM CET
user@ubuntu:~$ sudo bash
[sudo] password for user: 
root@ubuntu:~# ip link add name lxcbr0 type bridge
root@ubuntu:~# ip link set lxcbr0 up
root@ubuntu:~# exit
user@ubuntu:~$ /usr/lib/x86_64-linux-gnu/lxc/lxc-user-nic a b $$ veth lxcbr0 foobar
foobar:vethQ1C4AQ
user@ubuntu:~$ ip link show foobar
6: foobar@vethQ1C4AQ: <BROADCAST,MULTICAST> mtu 1500 qdisc noop state DOWN mode DEFAULT group default qlen 1000
    link/ether 8e:6e:3b:96:66:c6 brd ff:ff:ff:ff:ff:ff
user@ubuntu:~$ uname -a
Linux ubuntu 4.8.0-32-generic #34-Ubuntu SMP Tue Dec 13 14:30:43 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux
user@ubuntu:~$ cat /etc/lsb-release 
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.10
DISTRIB_CODENAME=yakkety
DISTRIB_DESCRIPTION="Ubuntu 16.10"
user@ubuntu:~$ cat /etc/apt/sources.list
# 

# deb cdrom:[Ubuntu-Server 16.10 _Yakkety Yak_ - Release amd64 (20161012.1)]/ yakkety main restricted

#deb cdrom:[Ubuntu-Server 16.10 _Yakkety Yak_ - Release amd64 (20161012.1)]/ yakkety main restricted

# See http://help.ubuntu.com/community/UpgradeNotes for how to upgrade to
# newer versions of the distribution.
deb http://ch.archive.ubuntu.com/ubuntu/ yakkety main restricted
# deb-src http://ch.archive.ubuntu.com/ubuntu/ yakkety main restricted

## Major bug fix updates produced after the final release of the
## distribution.
deb http://ch.archive.ubuntu.com/ubuntu/ yakkety-updates main restricted
# deb-src http://ch.archive.ubuntu.com/ubuntu/ yakkety-updates main restricted

## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team. Also, please note that software in universe WILL NOT receive any
## review or updates from the Ubuntu security team.
deb http://ch.archive.ubuntu.com/ubuntu/ yakkety universe
# deb-src http://ch.archive.ubuntu.com/ubuntu/ yakkety universe
deb http://ch.archive.ubuntu.com/ubuntu/ yakkety-updates universe
# deb-src http://ch.archive.ubuntu.com/ubuntu/ yakkety-updates universe

## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu 
## team, and may not be under a free licence. Please satisfy yourself as to 
## your rights to use the software. Also, please note that software in 
## multiverse WILL NOT receive any review or updates from the Ubuntu
## security team.
deb http://ch.archive.ubuntu.com/ubuntu/ yakkety multiverse
# deb-src http://ch.archive.ubuntu.com/ubuntu/ yakkety multiverse
deb http://ch.archive.ubuntu.com/ubuntu/ yakkety-updates multiverse
# deb-src http://ch.archive.ubuntu.com/ubuntu/ yakkety-updates multiverse

## N.B. software from this repository may not have been tested as
## extensively as that contained in the main release, although it includes
## newer versions of some applications which may provide useful features.
## Also, please note that software in backports WILL NOT receive any review
## or updates from the Ubuntu security team.
deb http://ch.archive.ubuntu.com/ubuntu/ yakkety-backports main restricted universe multiverse
# deb-src http://ch.archive.ubuntu.com/ubuntu/ yakkety-backports main restricted universe multiverse

## Uncomment the following two lines to add software from Canonical's
## 'partner' repository.
## This software is not part of Ubuntu, but is offered by Canonical and the
## respective vendors as a service to Ubuntu users.
# deb http://archive.canonical.com/ubuntu yakkety partner
# deb-src http://archive.canonical.com/ubuntu yakkety partner

deb http://security.ubuntu.com/ubuntu yakkety-security main restricted
# deb-src http://security.ubuntu.com/ubuntu yakkety-security main restricted
deb http://security.ubuntu.com/ubuntu yakkety-security universe
# deb-src http://security.ubuntu.com/ubuntu yakkety-security universe
deb http://security.ubuntu.com/ubuntu yakkety-security multiverse
# deb-src http://security.ubuntu.com/ubuntu yakkety-security multiverse
user@ubuntu:~$ exit

Script done on Fri 13 Jan 2017 11:42:07 AM CET