MySQL Job failed to start
Reinstallation will works because it will reset all the value to default. It is better to find what the real culprits (my.cnf editing mistake does happens, e.g. bad/outdated parameter suggestion during mysql tuning.)
Here is the mysql diagnosis if you suspect some value is wrong inside my.cnf : Run the mysqld to show you the results.
sudo -u mysql mysqld
Afterwards, fix all the my.cnf key error that pop out from the screen until mysqld startup successfully.
Then restart it using
sudo service mysql restart
My problem was running out of memory. Digital ocean has great instruction for adding swap memory for Ubuntu: https://www.digitalocean.com/community/tutorials/how-to-add-swap-on-ubuntu-14-04
This solved the issue and enabled me to restart the Mysql that otherwise would not start.
First make a backup of your /var/lib/mysql/ directory just to be safe.
sudo mkdir /home/<your username>/mysql/
cd /var/lib/mysql/
sudo cp * /home/<your username>/mysql/ -R
Next purge MySQL (this will remove php5-mysql and phpmyadmin as well as a number of other libraries so be prepared to re-install some items after this.
sudo apt-get purge mysql-server-5.1 mysql-common
Remove the folder /etc/mysql/ and it's contents
sudo rm /etc/mysql/ -R
Next check that your old database files are still in /var/lib/mysql/ if they are not then copy them back in to the folder then chown root:root
(only run these if the files are no longer there)
sudo mkdir /var/lib/mysql/
sudo chown root:root /var/lib/mysql/ -R
cd ~/mysql/
sudo cp * /var/lib/mysql/ -R
Next install mysql server
sudo apt-get install mysql-server
Finally re-install any missing packages like phpmyadmin and php5-mysql.