Sus dos primeros comandos no fueron ejecutados como root, por lo que es un comportamiento esperado. Necesitas ser root para parar/arrancar mysql.

Sin embargo:

sudo /etc/init.d/mysql start

debería funcionar. En efecto, a mí me funciona:

kojan:~> sudo /etc/init.d/mysql restart
[sudo] password for chris: 
Stopping MySQL database server: mysqld.
Starting MySQL database server: mysqld.
Checking for corrupt, not cleanly closed and upgrade needing tables..

Usé reiniciar en lugar de iniciar, ya que ya estaba funcionando, pero el efecto es el mismo. ¿Estás seguro de que has introducido tu contraseña correctamente? :) ¿Has editado la configuración de sudo para que no funcione?

Esta..

sudo /etc/init.d/mysql - root -p start

Los argumentos son incorrectos. un script init.d sólo toma start o stop o restart - sólo una palabra que le dice qué hacer. No puedes darle múltiples argumentos como estabas tratando de hacer.

De todos modos, la respuesta corta es la que realmente conseguiste que funcionara, es la forma recomendada. El service está reemplazando a todos los scripts init.d con el tiempo, así que deberías acostumbrarte a usar el service. La página que enlazas es de hace 3 años así que hay que tomarla con algo de sal :)

También ayuda a comprobar que "mysql" es el nombre de servicio correcto. En mi caso no lo era. Seguí recibiendo la siguiente respuesta: mysql: servicio no reconocido cuando se ejecuta

service mysql status 

Entonces comprobé /etc/init.d y encontré un script llamado mysqld que indicaba el nombre del proceso: mysqld y prog=mysqld

Entonces hice

service mysqld status
service mysqld stop
service mysqld start 

y todos funcionaron bien.

Para Ubuntu 12.10 y posteriores:

START MYSQL:

sudo start mysql

RESTART MYSQL:

sudo restart mysql # The service must be running

PARAR MYSQL:

sudo stop mysql # The service must be running