I had this same problem a few months ago and it drove me crazy for a couple of hours. I was so focused on clearing on the icon cache and thinking that it was just some sort of caching issue that it didn't immediately occur to me what the real problem was.
The answer, for me at least: Even though you have a 16x16 version of your image in your .ico file, Visual Studio will instead use the 32x32 image and scale it down to 16x16, causing it to look distorted. I say VS did it because when I ran the executable on other machines (different Windows OS's), I saw the same behavior so it wasn't a Windows 8 issue, for me. (It might very well be a Windows issue in general though, I don't know. I did not take the time to verify what was actually inside of the generated .exe--did it contain MY 16x16 version, or 16x16 version generated by scaling down my 32px version? That would have confirmed it, I guess...)
My "aha" moment came when I added a few rows of red pixels to each size of my icon image, in a different section of my icon. So I put the red rows in my 16x16 at the bottom. My 32x32 had the red rows in the center, etc. So then I added this .ico to my project and started the project up and BAM, there was a distorted version of my 32x32 icon being used in the system tray as my notify icon. There was no doubt about it.
If you notice that your notify icon (at 16x16) looks more distorted than you would expect, you might use a similar strategy to see if this same automatic scaling is happening. When I figured this out, my quick solution was to add a .ico to my project that contained ONLY the 16x16 version of my icon image. I then use that resource image only for my notify icon. Obviously, if you did this (have a 16x16 only image) for forms, for example, you would see a very distorted icon in your taskbar, Alt-Tab list, etc., because Windows has no choice in that situation but to create the different icon image sizes by scaling your 16x16 because that's all that you supplied. Anyway, in my particular case, as I believe is yours as well, there was no issue using the .ico for forms--they show the actual embedded 16x16 version of the image and there is no "automatic downsizing" of the 32px version.
That's all I know. I did not spend anymore time on this issue because I had to move on. I hope this helps someone avoid some icon frustration. Why, oh why, VS would you do this to us!?