Why does this image look so bad when dithered with a certain palette?
I think what's going on is something analogous to CCD sensor blooming.

The badly working palette does not cover the extreme color values of the original image. Floyd–Steinberg dithering works by error diffusion, where the error in color at a pixel being processed is spread to nearby pixels not yet processed, to the right and to some of the pixels on the next pixel row. With the kitten, you have near-black and near-white areas, and in those areas the algorithm – working like a bulldozer – will accumulate more and more error because the colors it can use will always fall short the same way, and when it finally comes out of the problem area, the accumulated error is so large that it takes many pixels to get rid of it, smudging the image.

In other words, if the image has out-of-gamut colors, you get problems. If a color is inside any polyhedron formed by any of the palette colors, then it is in gamut and can be reproduced by alternating colors from the palette. In other words, the color is in the convex hull of the palette colors. If it's not in the convex hull of the palette colors, it is out of gamut. Gamut mapping before dithering would resolve the problem.