Here's a further clue:
exactly the same problem occurs on my personal computer --- IONITX with Intel Atom 330, 3.2 GB memory, _and_ an even faster SSD, the Intel X25E. CUPS worked fine on that computer under Karmic; it was upgraded to Lucid when Beta 1 was released and the cups daemon has been failing to start since then.
Good luck bug hunters! This might be a tough one. It is real. Find it!
p.s. of course if it IS caused by a dreaded race condition then of course it sometimes goes away when software is re-installed or any odd change is made that happens to change the timing of events at boot time.