Regardless of the platform you used to install Vim, it's good to make sure that, with Vim, all the right features enabled. On a command line, run the following command:
$ vim --version
You will see the following output, with a set of features having a + and a - in front of them:
In the preceding screenshot, you can see that my Vim was actually compiled with Python 2 support (+python) instead of Python 3 support (-python3). To correct the issue, I'd have to either recompile Vim with +python3 enabled or find a package which distributes a compiled version of Vim with +python3 enabled.