Tim,
I designed in MicroC/OS-II into our design and I'm loving it. Truth be told, I've been trying to use it at work for a long time but never found a project for it until now. The configuration under the original Nios is a bit clunky. I purchased the Microtronix RTOS dev kit for Nios so this made it a bit easier. But, with the new Nios II it is totally integrated with your Nios II design. You can configure the OS to contain just what you need for your project. I haven't actually gotten a quote for the licensing yet but I talked to Labrosse and crew at the San Francisco ESC and the ballpark quote they gave me was orders of magnitude less than the VxWorks license we have on our other products.
I would recommend upgrading to Nios II and trying out MicroC/OS-II. It comes with the Nios II install so you really have nothing to lose
dave