We too had the same problem exactly on Lucid Lynx, while not having it on earlier Ubuntu releases. You know you're hitting the same issue if:
- mysql error log says it can't bind to that address or the address doesn't exist or something like that (can't remember the exact wording)
- mysql works perfectly if you start/restart it after booting the system
Seems like Ubuntu 10.04 tries to start MySQL before having assigned ip addresses to all network interfaces, so you don't actually have your ip setup when it starts.
We workarounded it by binding mysql to the 'any' address (0.0.0.0) and opening an hole for its port in our iptables (which is default closed for any traffic on any port on any ip).