Open Synaptic, do a reload, and then type VLC into a search box - that will bring up VLC.
Right click the VLC entry and choose "Mark for Installation"
Now on the top toolbar, press the Apply icon.
Wait for it to install and that's it.
It will now be in your main Menu.
If you need anymore help please post back,