OK, so here's what I've done.
I built a Console application in C#. I gave it an application icon in the property sheet of my .csproj. I build. I run. It's just fine. The icon shows in my taskbar just fine. When I hit Alt+Tab to switch windows, the icon shows there as well.
I added a registry entry in HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Run so that the console app starts with Windows. When the very same app starts with Windows, it has the default generic console app icon. If I close the app and restart it manually, the correct icon shows in the taskbar.
What the deal?
C#, .Net 4.5, Windows 7 Professional 64-bit