I just did a 60 second test of Paint on my Windows 7 computer (the first time I have *ever* launched paint.exe on a computer newer than Windows X) and I was able to immediately conclude that it is *still* worthless for 16-color pixel art.
When you save in 16 color mode, instead of saving a palette of the 16 colors you actually used in the drawing, it will flatten the colors in your image to fit into its own arbitray never-useful palette of 16 colors.
You are going to need to get a different graphics editor, I don't think there is any way to avoid that, sorry.
You said you like something simple, so I won't recommend <a href="
http://gimp.org/">The Gimp</a> because it is anything but simple (although I love it), but what about <a href="
http://code.google.com/p/grafx2/">Graphx2</a> (disclaimer: I haven't use grafx2 much myself, and don't actually know if it fits the "simple" requirement either)?
Maybe other people have some other suggestions.