I just set up a new 16.04 VM. I wanted to make sure that Python 3 was the default version on the system.
I noticed that:
$ ls -al /usr/bin/python
lrwxrwxrwx 1 root root 9 Jan 1 12:12 /usr/bin/python -> python2.7
I thought I was being smart and changed that link to point to python3.5. Once I changed it though, I couldn't seem to do any simple updates or installs without getting the dpkg error.
So if you're getting the dpkg error, check where /usr/bin/python is pointing to. If Python 3, that may be your issue.
