I got this error while trying to export a release build for an AIR application (with icons) in Flex Builder. The problem was pretty clear, it was missing the 32 pixels icon that I specified in the -app.xml file, but there was no mention of the 16,48 and 128 versions which meant that they were ok.

So first I tried to re-export the 32 pixels version hoping that the first one was corrupt. Still no luck. I also triple-checked to see that the path is correct, but the error persisted.

Then I decided to take a deeper look over the export Release Build wizard. At step 3 it asks for the AIR File Contents to include in the air file. There, in the icons folder I was shocked to notice that my 32 pixels png was not present. After a few cleans and refreshes on the project I was still stuck with the error. It was then when I noticed that I had the same file used as the title bar icon and for that I embeded it. So Flex Builder of course thought that I don't need to include it in the .air file since I already embeded it in the .swf, hence the nasty error. So I duplicated the file, and used one for embeding, one for the icons tag in the -app.xml and it was all fine from there.

So in case you get this nasty error this is what you should check:
1. Check if paths are correct. They must be relative to the src folder and in Windows use "/" to mark subfolders. Also remove xml nodes for icons that you don't have (eg if you don't have 16 px icons, just remove the image16x16 node, don't leave it blank).
2. Try to re-encode/export the file. Maybe Flex has problems decoding it.
3. Go to the 3rd step in the Export Release Build wizard and make sure that the iocn is checked in the list.
4. If at step 3 you don't find the icon in the list, it might be because you have an Embed directive for that file in your project.