I suppose you're right, if you actually "reduce" to 256 instead of starting out only allowing 256 in the first place.. MSPaint hasn't failed me yet!

I have used IDraw before though, it isn't too bad - my impression of it is that it's basically MSPaint with random extras.