Error with 'lsb_release -a' in Ubuntu 16.04 Xenial

I am having the same issue as you, but I was able to solve the problem after looking at the file /usr/bin/lsb_release.

The beginning of the file is #!/usr/bin/python3 -Es, meaning that it is using the python interpreter in /usr/bin/python3.

In my system, that file was a symlink to python2.7.

I fixed the issue by removing the symlink /usr/bin/python3, and then replacing it with the correct symlink to python3.5:

sudo ln -s /usr/bin/python3.5 /usr/bin/python3

Sorry to reply this 'old' post.

I also encountered this 'lsb_release -a' error these days in Ubuntu 17.10. I finally solved this issue by

sudo rm -rf /usr/bin/lsb_release

If I keep this file in computer, even if I specify a correct python directory in it, it gives me the errors: subprocess.CalledProcessError: Command 'lsb_release -a' returned non-zero exit status 1.

So, I deleted it in my computer and it works.