I could’ve saved so much time today if only I’d known some things. There are many Ubuntu/Linux related things that are just way too hard to do, and way too difficult to find on the web, even with Google. Here’s one gem to fix the problem in the title:
1: Start Synaptic: System->Administration->Synaptic Package Manager
2: Add Multiverse and Universe repos: Settings->Repositories, +Add, check them all, OK, OK
3: Search for VNC, mark and install the things you want