We've been using NB under Redhat Enterprise Linux since 4.5. In the beginning I felt as if we were beta testing the software for Veritas, lots of strange problems and lengthy tech support calls. However, since 5.1 and now with 6.0, it's been much more stable and quite easy to work with. I haven't actually deployed 6.0 yet and I'm adding a bunch of hardware (like a disk staging storage unit) to the mix but from the testing I've done I'm pretty sure it'll work well.
It's odd that you're switching away from Solaris. From what I've heard it's really the best OS for NB. What made you drop it?