Unable to launch Variety (AttributeError: 'module' object has no attribute '_base')

I am using Ubuntu 16.04 LTS. On installing variety following the instructions mentioned at http://peterlevi.com/variety/how-to-install/, I attempted to launch variety through dash. It tried to launch for a few seconds and then auto-closed. When I tried to launch it from the terminal, I got the following error:

Traceback (most recent call last):
  File "/usr/bin/variety", line 38, in <module>
    import variety
  File "/usr/lib/python2.7/dist-packages/variety/__init__.py", line 111, in <module>
    from variety import VarietyWindow
  File "/usr/lib/python2.7/dist-packages/variety/VarietyWindow.py", line 22, in <module>
    from variety.FacebookHelper import FacebookHelper
  File "/usr/lib/python2.7/dist-packages/variety/FacebookHelper.py", line 55, in <module>
    from variety.Util import Util
  File "/usr/lib/python2.7/dist-packages/variety/Util.py", line 16, in <module>
    import bs4
  File "/usr/lib/python2.7/dist-packages/bs4/__init__.py", line 30, in <module>
    from .builder import builder_registry, ParserRejectedMarkup
  File "/usr/lib/python2.7/dist-packages/bs4/builder/__init__.py", line 314, in <module>
    from . import _html5lib
  File "/usr/lib/python2.7/dist-packages/bs4/builder/_html5lib.py", line 70, in <module>
    class TreeBuilderForHtml5lib(html5lib.treebuilders._base.TreeBuilder):
AttributeError: 'module' object has no attribute '_base'

How do I fix this and get variety to launch normally?