One option on debian-based systems is to use the debian-sys-maint user. Login info is in /etc/mysql/debian.cnf -- be sure to specify the host as well, even if it's localhost. Once you're in, you can set the password for mark (drop the user first, if it already exists).
$ mysql -u debian-sys-maint -h localhost -p
mysql> CREATE USER 'mark'@'localhost' IDENTIFIED BY 'mypass';
mysql> GRANT ALL ON *.* TO 'mark'@'localhost';
mysql> GRANT GRANT OPTION ON *.* TO 'mark'@'localhost';
mysql> FLUSH PRIVILEGES;
$ shred -u ~/.mysql_history
EDIT: After reading the linked instructions that you followed, it's not clear that mysql is listening on localhost, which is necessary if all your users are 'user'@'localhost', since mysql user accounts are bound to a host from which they access the mysql server. If the server is listening on an address other than localhost, even if you're accessing it from the local machine, you'll need to use the address it's listening on. If this is the case, set it to listen on 127.0.0.1 or localhost, log in as root or debian-sys-maint, and add accounts for
'mark'@'<other ip>' and
/etc/hostname should not be
localhost but rather the machine name. I don't think this has anything to do with your troubles, but it could. Try changing it to something else (
marksmachine for example) by editing /etc/hostname and then
$ sudo hostname -F /etc/hostname.