Since the command you mention includes apt
I suppose you're on debian or a linux distribution based on it (ubuntu, mint).
I've looked on ubuntu's website and found a vim-gnome package for the latest LTS (14.04).
Its version is 7.4.052 which is not enough if blowfish2 support was added in version 7.4.399.
If you're on ubuntu 14.04, to install a more recent version of vim-gnome, you could add this ppa to the list of your repositories :
sudo add-apt-repository ppa:pi-rho/dev
Then update and upgrade.
The latest version of vim-gnome from this ppa is 7.4.899, which should be enough.
Since there are different versions of vim, with different features (vim-tiny, vim-gnome ...), you could also check that you're calling the desired version by typing :
sudo update-alternatives --config vim