In one of yesterday's reviews I mentioned MagCloud as a viable alternative to Lulu for print-on-demand gamebooks. Caveats include that they only do 8.5" x 11" books in the 4 to 100 page range, they may only offer staple-bound (I'm not sure on that point) and it costs 20 cents a page. On the plus side that 20 cents gets you full color.
My buddy Pat sent me a link to Ka-Blam as another possibility. They're set up to do POD comics and manga. Their 5" x 7.5" manga format is mighty close to the booklet formats of which I am so enamoured. Publishing my Miscellaneum of Cinder through them would cost less than half as much as Lulu, allowing me to lower the price and/or increase the profits dramatically. Ka-Blam offers an option where they will lower the unit cost if you agree to them inserting a full page ad into the work, either on one of the inside covers or the back. Which also bring up another point: Lulu doesn't let you print anything on the inside covers as far as I can tell. That's two blank surfaces the customers are paying for that could be filled with content.