自分の環境のVimでは :echo has('python3') は1なのですが、NeoVimは0です。どうやら$VIMRUNTIMEがおかしいのではないか(/usr/share/vim/vim73になっている)というところまではたどり着いたのですが、そこからがわかりません。
たぶんインストールが失敗しているので、install from sourceを見てやってみました。しかし、それでも$VIMRUNTIMEがおかしいままです。$VIMは/usr/local/share/nvimになりました。
pip3 install neovimでpythonのインターフェースはインストールできています。どのようにしたら :echo has('python3') が1になりdeoplete.nvimが使えるようになるのでしょうか?