Well, it works. I needed to install java and manually register the plugin with Mozilla, but it works. The good news is that it works, and it's pretty damn cool. The bad news is that the java plugin slows the launching of Mozilla way down.
What's worse is that registering the java plugin causes Firebird not to launch at all. This tek-tips thread explains the problem and gives a quick solution - don't register the java plugin with Firebird. I think the issue may be that I registered the plugin with Firebird in the same way I did with Mozilla. I'll look into the proper way of registering it.
NewsMonster itself is great. It's got the familiar 3-pane interface and has the neat "website filters" feature - which grabs headlines and thumbnailed screenshots of non-RSS-enabled sites like CNN. The news items themselves are rendered with a standard stylesheet, but the right-click context menu is that of Mozilla, which allows me to open links in a new tab right from the aggregator. Very cool, exactly what I was looking for. It also allowed me to import my .opml from NetNewsWire, however it didn't leave my folders in tact. But again, it's slow but I think the biggest issue is that I'm running RedHat 9 on an 800mhz laptop with 128mb of ram - so things are bound to be slow.
Update: Turns out I was registering the wrong Java plugin with Firebird. The Java plugin and the Firebird browser need to be compiled with the same version of gcc - in my case, 3.2. Using Firebird makes NewsMonster a bit quicker, but overall it's still crawling along (which again, is probably just the system). I can't wait until Apple and Mozilla get their problems sorted out so I can start using this software day-to-day.