GIF file size increases dramatically after conversion to sRGB

Hi!

I was saving an image for web using Save for Web and noticed something odd. When I first went to Save for Web, the projected GIF file size was about 3 or 4 kb with 64 colors and 100% diffusion dither. However, I noticed that I had forgotten to convert the file to sRGB, so the colors were looking muddy.

I cancelled out of Save for Web, converted to sRGB (Image>Mode>Convert to Profile), then went directly back into Save for Web. But this time, with 64 colors and 100% diffusion dither, my projected GIF file size was 120 kb!

Any thoughts as to why this might be?

Thanks!
Candace

It seems that the issue is with the 21st color. If I bring it down to 20 colors (100% diffusion dither), the projected file size is 3.753 kb, but then when I nudge it up to 21 colors (no other changes) the projected file size jumps to 36.71 kb.