Problem solved! You were right - it was GIMP's antialiasing. Ironically, not on the brush, this is what had confused me as I deliberately turned that off. It was the MAGIC WAND tool that had aliasing enabled. For the existing sprites, I had to edit them close up and get rid of all the aliased pixels around the edges. now it looks perfect. 
Thanks again !

Thanks again !