If you cannot install new packages using the terminal under Ubuntu 13.04/12.10 or older and you receive this type of error:

(...) You might want to run 'apt-get -f install' to correct these:
The following packages have unmet dependencies: (...)

You may try these various types of solutions that may help you repair your package database:

   Tip 1 

Via the terminal, enter this command to fix broken packages:

sudo apt-get --fix-broken install

   Tip 2

If the above command didn't help, try these ones:

sudo rm /var/lib/apt/lists/* -vf   
sudo apt-get update 

   Tip 3

You may also try these commands:

sudo apt-get clean  
sudo apt-get autoclean 
sudo apt-get autoremove

   Tip 4

Another useful commands:

sudo dpkg --configure -a 
sudo apt-get update

    Tip 5

Open Ubuntu Software Center and if prompted to repair broken packages, click simply the repair button.

Note: these tips are also workable under Linux Mint.