There is nothing particularly special about making icons - they're just bitmaps on small canvases. And there’s certainly no need to submit yourself to the torture of MSPAINT (which should be reserved for free-handing intentionally bad drawings. ;-) ).
Depending on your budget, I would suggest these programs:
Paint.Net (free!)
Relatively simple & easy to use. Feels like MSPaint with enhancements. Good free program.
Photoshop ($700)
King of the hill, but priced accordingly. You can do just about anything with Photoshop.
Other programs that are commonly used (but I don't personally use):
The GIMP (free!)
I find the interface confusing and obtuse, but this could be the result of years of Photoshop training me to work a certain way. Many people swear by this program. S.gfx also pointed out that has many advanced features and allows saving as ico. Even if not chosen as primary editor, it is a good idea to have it installed.
CorelDraw ($325)
I know that people use this program, I just don't know people that use this program.
If you want to create icons that will easily scale to future monitor resolutions (which seem to always be increasing), you'll want to create in a vector-based design program:
If you need a program to convert your bitmaps to ICO files, IcoFX is great and it has a shareware version. Update: I forgot to mention (because it's not part of my workflow), IcoFX also has editing capabilities so you can create an icon from scratch without using any other programs. Interface is similar to MSPaint or Paint.NET.