Thanks to your persistence I just tweaked just about every knob there is to tweak and discovered this: once the following preferences are set and Firefox is restarted, the issue appears.

user_pref("extensions.autohidestatusbar.alwayshide", true);
user_pref("extensions.autohidestatusbar.showondownload", false);
user_pref("extensions.autohidestatusbar.showonpageload", false);
user_pref("extensions.autohidestatusbar.showstatusbaritem", false);
user_pref("extensions.autohidestatusbar.timer", 300);
user_pref("extensions.autohidestatusbar.usePanel", true);

(I hope this gets formatted correctly.)

There are two traps here as far as I can see. The first is that once .alwayshide is set to true (i.e. ”Always hide” is selected in aHS’ preferences), the state of .usePanel can’t be changed through the GUI (”Floating statusbar”), and yet, it does make a difference. So it has to be unset before ”Always hide” is selected. Apparently a defect in the add-on’s design, though I see why it might make sense, were it not for the issue at hand (which is a defect unto its own).

The other trap is that the issue of script installing links doing nothing (as described above) doesn’t manifest itself until Firefox is restarted. So to see it you have to turn on ”Floating statusbar”, then (possibly) ”Always hide”, then restart Firefox and boom: Install links have stopped working.

There’s still a chance this might not be the case for you: I’m running Firefox from the distro repositories on Ubuntu 10.04, and Greasemonkey on this setup also comes from the repos. So if you still can’t reproduce this, you may be running the newer version of GM (0.8.20100211.5-1ubuntu2 here, with 0.8.20100408.6 being the latest release on addons.mozilla.org).