I love this program. It is still used by industry level professionals when it comes to low-res pixel art. (truly a lost skill) The original was version 1.0 released July 1998 as a stand alone product. Later it came bundled with photoshop but the original is still the best. It can still be found on sites like ebay and amazon for a reasonable price.
Paint.net is overkill for creating sprites. It's best to use something low resolution although you may achieve nice results with something like Photoshop it was not created with pixel artists in mind. Anyone like to post some examples of their work?