It's true that in a 16X16 area 16 colors is all you need. But if you want to have a presence on the users desktop it is nice to have a high quality icon. Now I'm not an artist but I'm guessing you can make a lot better icon from 256 colors rather than 16. A good example of this is WinZip. They have a 16 color icon for those people who's computers do not suport 24 bit or higher color, but if your computer does support that they have a really nice high color icon.

Rip