The reason for this is that the picture you are hiding is being reduced from 24 bits to 3 bits. You have to expect a great deal of quality loss during that process.
You can see what your picture will look like by using the Preview check box.
Also, you can dither your picture before encoding it since dithering will yeild a higher quality than what I'm doing.
So, basically, it is working as designed.