@Broni - I've tried that already. What happens is that, though the button appears in the right-click menu for other items, for some reason it doesn't for the specific .exe. Leads me to believe it's a problem with the context menu, although why it doesn't work only for the troubled file is beyond me - it works fine with others.
@smeezekitty - I've tried system restore for the shortcut thing, but the fact is that I didn't realize I had this problem before I cleaned out my restore points, so, uh, yeah. It didn't fix anything.
So, does it sound like I'm doomed to have a random file on my computer and have half of the shortcuts not work? The file itself is less than 1mb, although the .lnk thing is pretty annoying.