Cannot install programs with apt-get or Software Center

mc and fortune are both in the universe repository. Make sure you have the option to download and install packages from universe enabled.

Open software-center. Go to Edit menu --> Open software sources and check Universe option.

software-sources-gtk

After checking the option, run the following commands to install mc and fortune.

sudo apt-get update
sudo apt-get install mc fortune

Try this

sudo apt-get install ubuntu-restricted-extras

and then this

sudo apt-get update && sudo apt-get upgrade

and then try your commands


After you install Ubuntu, run:

sudo apt-get update && sudo apt-get upgrade

This will update the package lists and upgrade your system.

However, if you've already done so, you can follow the instructions given by jokerdino.