See Launchpad: https://bugs.launchpad.net/ubuntu/+source/mysql-dfsg-5.1/+bug/566736
There is a bug with Ubuntu 10.04's MySQL server. If you have it bind to a specific interface, it will fail to start on reboot because it attempts to start after any network interface (such as 127.0.0.1) is initialized. If the interface that MySQL is bound to isn't reinitialized, it will hang. If you try to remove any specific interface bindings from the my.cnf settings, you'll run into another problem port assignment. You need to make sure that the upstart init script matches the bind-address value in the my.cnf file.
My edits:
/etc/mysql/my.cnf
# Instead of skip-networking the default is now to listen only on # localhost which is more compatible and is not less secure. bind-address = 127.0.0.1 #
/etc/init/mysql.conf
start on (net-device-up IFACE=lo and local-filesystems and runlevel [2345]) stop on runlevel [016]
Note the IFACE=lo addition to the start on line.
My thanks to cdenley's post on the Ubuntu forums for shedding light on the problem.