The short version is that I now know way too much Drupal for my own well being.
patch in #9 didn't work for me. I don't think you can simply manipulate the array you get from drupal_add_js() and drupal_add_css() and expect your changes to persist through later preprocess functions. Those two functions keep an internal array with js and css data, so you have to use them. I re-rolled a patch that works for me and also removed a .buildpath and .project file inadvertently included in the same patch. Nodereference explorer is working for me now.
Optimize Javascript (and CSS too) breaks Nodereference Explorer | drupal.org
On the upside, Nodereference Explorer project is a great concept for providing a better UI when relating one node to another in drupal. Its supposed to pop up a Modal window with a richer interface that allows users to filter and search for the desired node. Unfortunately, neither the "stable" nor "development" versions worked for me. I had to break out the firebug and tweak a patch I found in the bug report above to get it working.
Hopefully there aren't any more issues in this module, as I really need it to work in my current project.