Perhaps the vim executable isn't in your path, so it doesn't know where to find it when you type the command.
^ that will check to see if a program named vim is in any of the common locations on your system. If it is, then you need to updated your PATH environment variable so it knows where to find it.
sudo apt-get install -y vim
^ that should install it, but you may have already attempted that.