None of the answers worked for me (I am using Ubuntu 16.04 and Python 3.6). So I finally solved the issue as following:
1- connect to the FTP of the server
2- go to the folder "/usr/lib/python3/dist-packages/"
3- duplicate the file "apt_pkg.cpython-35m-x86_64-linux-gnu.so"
4- rename this duplicated file to "apt_pkg.cpython-36m-x86_64-linux-gnu.so"
That's it!