Icon design falls into the "hard" category in my book. It really breaks down to a minimal conveyance of an idea that also has to be attractive and fit into the rest of your design. This is a rather good breakdown of the various mistakes you see in various operating systems and applications.
In the old days, you worked with a 16x16 or 32x32 canvas and pixel by pixel painted your icon. Now, (at least in KDE... I'm not sure how Gnome, Windows or OSX handle it) you can design with SVG (scalable vector graphics) which I think is a huge step in the right direction but I don't think it reduces the underlying challenge.