I have tried everything to install MariaDB on this clean Ubuntu installation but I keep getting this error,

Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
mariadb-server : Depends: mariadb-server-5.5 (= 5.5.33a+maria-1~saucy) 
but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

I have followed this guide to try and install it, http://www.unixmen.com/install-lemp-server-nginx-mysql-mariadb-php-ubuntu-13-10-server/

And I have also followed the "official" guide on the MariaDB downloads page for 13.10 https://downloads.mariadb.org/mariadb/repositories/

But nothing seems to be working.

Edit 1

I have tried both How do I resolve unmet dependencies? and How to install MariaDB? but it still gives me the error I posted above.

It's a fresh Ubuntu install with hardly anything installed.

Edit 2

All the check boxes are ticket in Updates. I ran:

sudo apt-get update && sudo apt-get -f install mariadb-server-5.5"=5.5.33a+maria-1~saucy"

And it gave me this error:

The following packages have unmet dependencies:
mariadb-server-5.5 : Depends: mariadb-client-5.5 (>= 5.5.33a+maria-1~saucy) 
but it is not going to be installed
Depends: mariadb-server-core-5.5 (>= 5.5.33a+maria-1~saucy) 
but it is not going to be installed
E: Unable to correct problems, you have held broken packages.