As I started my new WPF application, I got greeted with FileFormatException - "The image format is unrecognized". I was confused since application was so new that I haven't added any images to it. After checking and double-checking I found which image exception was referring to - my application icon.
It seemed like normal icon to me. As I compared it to icons that I already used successfully with WPF there was only one difference. This icon had 256x256 size. As soon as I deleted it, my program started working again (ok, it was empty application so making it work was not that big of task).
Side effect of this solution was that I lost my big images. That felt dirty to me so I ended up with two icons in my application. First one was with all images (including 256x256) and I used it as application icon (Properties, Application, Icon). Second one was without 256x256 images and I just set it's Build Action to "Resource". Whenever I needed WPF window icon, I just pointed to second one.
I must confess that I am quite annoyed by this. WPF was all about making Windows look and feel better. Using brand new .NET 4 and restricting icons to sizes before Vista just does not seem right. And I better not start about how useful XAML exceptions are...
P.S. If you do not have icon editor available, I would recommend IcoFx. It is good and it is free.