I am thinking that the answer to this question will vary in time because Apple constantly changes the application validation rules. These validation rules will surface only when you are submitting your app to the AppStore.
In this particular situation, the validation error happened to me while uploading the app on 08/03/2012.
The solution was fairly straight forward. I had to move to icon files which I had located in a folder nested within the project directory all to way up to the TOP LEVEL project directory - one that has the project file in it. Once I did that and readded the files back to the Resources in my project the validation error went away.
Of course you should check that this issue is not caused by misspelled filenames i.e. differences between your plist file and true names of icon files on your file system.