Registered just to respond to this thread. Found it trying to figure this one out myself, and eventually did figure it out.
Turns out a windows update caused this, and the red shortcut happens when there's additional hardlinks of a shortcut. If you right click them, go to properties, then the Link Properties tab and you'll see the other locations. Mine had hardlinks created under "C:\$WINDOWS.~BT\NewOS\Users\...". Once you delete the hardlinks to your afflicted shortcuts the red overlays disappear.