Mailing the story:
Paint.NET for Linux: Paint.Mono
Paint.NET is one of the best image editing applications for Windows and it has a version for Linux too, called Paint.Mono (or Mono Paint). According to Miguel de Icaza, most of the features in Paint.NET have been ported over to Paint-Mono, with more to come.