Nice stairs.

I really looks like you have anti-aliasing off.
I've been using GIMP for years (currently 2. and I've never had a problem like that.

As Tiana suggested, starting with a much larger image and scaling it down is another option.
If you do scale the image down, you'll get a much better result if you scale it down in steps of about 80%.
(i.e. with a starting image size of 100, scale it in steps like 80, 64, 50, 40, 32, 25... etc.)