Apparently, when I select pixels using the Lasso, colors may bleed out depending on how far in the pixel the lasso was, even if the pixel isn't part of the selection. I need the Lasso because I'm editing diagonal lines that aren't of the same color.
Here's a (crappy) before/after example with random colors:
With the Lasso I put the purple areas into a selection and use the fill bucket to fill the entire selection with a hot reddish orange color in a single click (first image to second image). It looks crappy, while ideally it should look like a simple palette swap like the third image.