I was pretty sure PhotoDeluxe could do it. What you're looking for is INDEX, not Grayscale. In Photoshop I would generally choose MODE->Grayscale and then MODE->RGB and then MODE->INDEX

PShop won't allow you to use the Index selector when you're already in grayscale (which itself is an 8bit index mode).

Anyway, take a look as I believe PhotoDeluxe should have at least those basic modes of Photoshop. Of course you might also want to try PhotoshopElements which was released last year. It's a very cut down PShop - I'm not sure if it replaced PhotoDeluxe in their lineup.

Bruno