Check if your /tmp has the right permissions. Mine, on a fairly clean xen VPS install was set to 755 and this prevented the creation of the root user during the installation of mysql-server package. chmod 1777 /tmp Then purge and reinstall mysql-server.