If you assigned a host name to your Linux when you installed it, mysql will choke and refuse to start unless you give the host name in the command. To see if you have a host name setup, look in /etc/hosts. Look for something other than localhost. Then use that hostname when you try to start mysql.
Like so: mysql -u root -h <hostname>