In my experience NaCl is not a viable platform at this time.
My friend and I spent a couple weeks just trying to get the developer tools to work. We tried on Ubuntu, OS X, Windows, and Arch Linux. We weren't able to get started on a single platform. In the process we came across bugs that were several months old that haven't been fixed, even on their supported platforms.
Another thing to worry about is whether NaCl will take off. We can't know how committed Google is and how many users will install the plugin. It was supposed to be enabled by default in Chrome 6 (I believe) but it still isn't enabled in 7.
NaCl is still promising (especially Portable Native Client) but Google has to get it working first.
The link in the paper to their Java implementation is now broken: does anyone have a current link?