I'd go looking a little harder at the NexBlack vs NexIA if I were to do it again today. NexIA was superceded by NexIA+ and (apparently) now is replaced by the NexBlack (which has just come on market and might be hard to find). Yah, the CF and AA batteries were the major points for me. I didn't like being limited by built-in memory size or battery style. The upgrade-able firmware was a good thing- seems like it was used as a way to get the product to market faster, though- fixing bugs after launch.
The Nex3 series looks cool, too, though. As a CF user, I am swung toward the others.
I bought my NexIA a couple of years ago, now, so I'm out of touch with what's what in the latest personal mp3 players.
Tell you what, Jon, if you want to try it out I'll lend it to you with a blank 256MB card in it. I don't fly much these days, so it just sits.
edit:
found this link to the Frontier Labs
store.