Today Lulu.com told me that:
Your document could not be created: This font is not embedded: Times-Roman
Even though I'm not using Times in my document, it was sneaking into the PDF as a Type 1 font. The .fo file doesn't have a reference to "Times" nor do my style sheets. I'm not sure where it's coming from, but the solution to this problem is to ADD Times to your list of embedded fonts even though you don't want to use it. Match the structure that you've got for your other fonts, but add in an extra line for "Times." I used the version of Times that comes in the Ubuntu package msttcorefonts.
Adding a real reference to a font you're not using will make Lulu.com love you.
If you're using LaTeX you might also want to check out the article LaTeX and Lulu.com. It's got some handy tricks that will work for other document processing tool chains as well.
A more detailed article on the whole tool chain will be coming soon.
Times-Roman is one of the 14
Times-Roman is one of the 14 predefined T1 fonts in the Adobe PDF spec, IIRC. I think it may even be used by default for text where you neglect to specify a font explicitly. That might explain where it comes from, even though your .fo file/stylesheets don't mention it. But since it's predefined, PDF files shouldn't have to embed it, which makes the lulu.com error message somewhat baffling.
msttcorefonts has Times New Roman, which is a slightly different True Type font (although it looks very similar, and intentionally has the same metrics).
And no, I've no idea why I'm writing this, since I haven't ever solved this problem nor encountered, nor even used lulu.com. Must be my "ooh, I have a piece of obscure information that wants to get out on the Internet" instinct at work.