The issue is likely due to socket authentication being enabled for the root user by default when no password is set, during the upgrade to ubuntu 16.04.

The solution is to revert back to native password authentication. You can do this by logging in to MySQL using socket authentication by doing:

sudo mysql -u root

Once logged in:

ALTER USER 'root'@'localhost' IDENTIFIED WITH mysql_native_password BY 'password';

which will revert back to the native (old default) password authentication.

Now use password as the password whenever required by MySQL.

Try opening services.msc from the start menu search box and try manually starting the MySQL service or directly write services.msc in Run box

It looks like there are a lot of causes of this error.

My Cause / Solution

In my case, the cause was that my server was configured to only accept connections from localhost. I fixed it by following this article: How Do I Enable Remote Access To MySQL Database Server?. My my.cnf file had no skip-networking line, so I just changed the line

bind-address = 127.0.0.1

to

bind-address = 0.0.0.0

This allows connections from any IP, not just 127.0.0.1.

Then, I created a MySql user that could connect from my client machine by running the following terminal commands:

# mysql -u root -pmysql> CREATE USER 'username'@'1.2.3.4' IDENTIFIED BY 'password';    -> GRANT ALL PRIVILEGES ON *.* TO 'username'@'1.2.3.4' WITH GRANT OPTION;    -> \q

where 1.2.3.4 is the IP of the client you are trying to connect from. If you really have trouble, you can use '%' instead of '1.2.3.4' to allow the user to connect from any IP.

Other Causes

For a fairly extensive list, see Causes of Access-Denied Errors.