You should be able to do this by stopping the MySQL server and restarting it up in safe mode where you will not be prompted for a password. You can then restore your root details and restart the server to normal operation. This guide provides steps to reset a lost root password but once in safe mode you should be able to re-add the user account that was deleted and grant permissions.

Ryan, Thanks for your quick response .. I was able to stop the MySQL server however the restart in safe mode failed (even when I did SUDO ...)

forge@smooth-sands:/$ mysqld_safe --skip-grant-tables &
[1] 2938
forge@smooth-sands:/$ 150424 10:16:25 mysqld_safe Can't log to error log and sys
log at the same time.  Remove all --log-error configuration options for --syslog
 to take effect.
150424 10:16:25 mysqld_safe Logging to '/var/log/mysql/error.log'.
touch: cannot touch ‘/var/log/mysql/error.log’: Permission denied
chmod: cannot access ‘/var/log/mysql/error.log’: Permission denied
cat: /var/run/mysqld/mysqld.pid: Permission denied
rm: cannot remove ‘/var/run/mysqld/mysqld.pid’: Permission denied
150424 10:16:25 mysqld_safe Fatal error: Can't remove the pid file:
/var/run/mysqld/mysqld.pid
Please remove it manually and start /usr/bin/mysqld_safe again;
mysqld daemon not started
/usr/bin/mysqld_safe: 126: /usr/bin/mysqld_safe: cannot create /var/log/mysql/er
ror.log: Permission denied

[1]+  Exit 1                  mysqld_safe --skip-grant-tables

I don't understand what is going on here.

When I do SUDO... I see the following:

forge@smooth-sands:/$ sudo /etc/init.d/mysql stop
 * Stopping MySQL database server mysqld
   ...done.
forge@smooth-sands:/$ sudo mysqld_safe --skip-grant-tables &
[1] 4622
forge@smooth-sands:/$ 150424 10:31:30 mysqld_safe Can't log to error log and sys
log at the same time.  Remove all --log-error configuration options for --syslog
 to take effect.
150424 10:31:30 mysqld_safe Logging to '/var/log/mysql/error.log'.
150424 10:31:30 mysqld_safe A mysqld process already exists

[1]+  Exit 1                  sudo mysqld_safe --skip-grant-tables
forge@smooth-sands:/$

OK I solved the issue: First I had to stop the SERVICE:

sudo service mysql start

Then I could restart in safe mode with skip-grant-tables

$ sudo mysqld_safe --skip-grant-tables &

And then restore the privileges

mysql> UPDATE mysql.user SET Grant_priv='Y', Super_priv='Y' WHERE User='root';

Then restart the service.

Thanks for your help.