Fatal Python error: Py_Initialize: Unable to get the locale encoding ... SyntaxError: invalid syntax Aborted (core dumped)

I would recommend unsetting PYTHONPATH. It is generally not needed, and it causes things to break like this by making one Python load things from another Python (in this case, it looks like the system's Python 3 is trying to load something that was written for Python 2).

I have been having similar issues in the past couple days, so I traced it back to how bash handles "command not found". In Ubuntu 14.04 (and Linux Mint 17, which I uses the 14.04 scripts), /etc/bash.bashrc has the following function:

if [ -x /usr/lib/command-not-found ]; then
    function command_not_found_handle {
        # check because c-n-f could've been removed in the meantime
        if [ -x /usr/lib/command-not-found ]; then
            /usr/bin/python /usr/lib/command-not-found -- $1
            return $?
        else
           return 127
        fi
    }
fi

However, /usr/lib/command-not-found has been rewritten for Python 3. It handles the /etc/bash.bashrc command with:

if sys.version < '3':                                                       
    # We might end up being executed with Python 2 due to an old            
    # /etc/bash.bashrc.                                                     
    import os                                                               
    if "COMMAND_NOT_FOUND_FORCE_PYTHON2" not in os.environ:                 
        os.execvp("python3", [sys.argv[0]] + sys.argv)

This calls "python3" from the path rather than giving the direct path. To correct this, line 22 of /usr/lib/command-not-found should be changed from

os.execvp("python3", [sys.argv[0]] + sys.argv)

to

os.execv("/usr/bin/python3", [sys.argv[0]] + sys.argv)

This appears to be a bug with Ubuntu rather than Anaconda. I will check to see if it appears in later distributions.

My problem was a bit different: As one user, I could run python, but as another user, not (I got the same error as OP). Finally, I found out that the permissions and ownership of /usr/lib/python3.5 were screwed. The reason for this was that I had recursively set the permissions and ownership on virtualenv, which ended up in modifying the symlink targets (targetin /usr/lib/python3.5) as well.

Tip: Use strace python to figure out what's going on during Python startup. When I used strace, I could clearly see PERMISSION_DENIED on /usr/lib/python3.5.