textlive-bibtex-extra and biber conflict
Solution 1:
Based on this bug report, it looks like what you've found (and what I've also just encountered) is a bug that didn't get fixed in time for 16.04 .
Someone on that page suggested a workaround which involves downloading biber from source. You can consider that until it is finally fixed?
(Just tried it myself and confirmed that it works.)
(Edit: Note that it seems (the older) biber version 2.4 should be used. A newer version doesn't seem compatible with the biblatex that comes with Ubuntu 16.04)