Andrew.
First Kudos to you and your plugin! I have it installed a few of my sites and am not having an issue except on one of them. This is a site I inherited with a few plugins so I am sure it is a conflict of some sort.
That being said, if I click in the text editor, or highlight my text and then press ALT, SHIFT, and A at the same time (your shortcut) the Link is no longer grayed out and also works as normal.
Tried your suggest above but to no avail, but there is a workaround to have it function.
Used IE9 and it worked up until the update to 3.6, but again just for one site that has a few plugins.