Uninstalled vim, now can't install it again

I have removeded vim-tiny to get full installation following this tutorial and now I can't install vim by:

$ sudo apt-get install vim
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Package vim is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source

E: Package 'vim' has no installation candidate

If I simply try to install vim-tiny again situation is same:

$ sudo apt-get install vim-tiny
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Package vim-tiny is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source

E: Package 'vim-tiny' has no installation candidate

Output of vim -version is:

$ vim -version
The program 'vim' can be found in the following packages:
 * vim
 * vim-gnome
 * vim-tiny
 * vim-athena (You will have to enable component called 'universe')
 * vim-gtk (You will have to enable component called 'universe')
 * vim-nox (You will have to enable component called 'universe')
Try: sudo apt-get install <selected package>

I have also tried sudo apt-get update and sudo apt-get upgrade and sudo apt-get dist-upgrade and it's all the same. I am using Ubuntu 14.04 LTS. It is very strange situation for me to perform sudo apt-get remove vim-tiny but can't perform sudo apt-get install vim-tiny after this. Any help?