Yeah I learned about the XPCNativeWrapper objects last night too. Basically GM has access to every object (from window/document on down) as one of these for security purposes (so the target page can't redefine standard methods). Due to the vagaries of the way they are implemented, you can't call the onclick/onkeypress/etc methods directly. It actually states in the documentation that addEventListener is the preferred (and only working) method.
You can supposedly get access to the underlying JS object from the XPCNativeWrapper object with the wrappedJSObject property and then act on it, but it's a big security no-no. I tried it anyway to no avail.
Your thought on the page not being loaded is kind of where I ended up too. However, my understanding was that GM ran user scripts after the window.onload finished, but I could be completely wrong here. If I assign all the links id attributes in the GM script and then manually add event listeners in my Firebug console, they work fine. Also, you'll notice that later in my script I add click listeners on other items (buttons and links) that work swimmingly, so it's either entirely arbitrary or I'm missing something very obvious.
Thanks for looking at this, I'll look forward to any other thoughts you have.
EDIT: Looks like I was very wrong about the GM script executing after the window load event. I have been playing with wrapping code in a load event listener and have indeed got it working that way. Thanks for the suggestion! I'll hopefully have something polished and posted soon.