We had similar network problem (and slow boot) with a virtual bridge. It appeared the culprit was a somehow misonfigured ebtables package. The following command solved it:
$ dpkg-reconfigure ebtables debian stable amd64 bridge-utils 1.4-5 ebtables 2.0.9.2-2 -- You received this bug notification because you are a member of Ubuntu Server Team, which is subscribed to bridge-utils in Ubuntu. https://bugs.launchpad.net/bugs/919068 Title: bridge_ports all doesn't work at boot time To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/bridge-utils/+bug/919068/+subscriptions -- Ubuntu-server-bugs mailing list Ubuntu-server-bugs@lists.ubuntu.com Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/ubuntu-server-bugs