I tried some tools for that, and what works best is PyxelEdit. Paint.NET works but has no tile specific tools, Krita, Photoshop or Gimp are overkill alternatives. GraphicsGale seems to be very good, but I find it hard to use.
Try the old beta of PyxelEdit, it's worth it. As soon as I start to need more gfx I will buy it.