I disagree that the regression is critical. IIUC, it fails on systems without urandom, such as Tru64 and HPUX. However, failure to support such systems is *not* critical, IMO; I think that OS-specific failures should be considered critical only if they occur on Linux, Windows, or OSX.

So I suggest that the priority of this issue is reduced.

More relevant than breaking HPUX is, IMO, that urandom is actually documented to raise NotImplementedError, so the patch looks good. For best compatibility, the actual spelling of the error message from 2.6 should be restored.

I'm puzzled by 

https://h20392.www2.hp.com/portal/swdepot/displayProductInfo.do?productNumber=KRNG11I

which claims that HPUX 11.11 (at least) *does* have /dev/urandom. Maybe your installation doesn't have KRNG11i in /etc/loadmods?

Also, the claim that it breaks Tru64 contradicts with

http://en.wikipedia.org/wiki//dev/random

which claims that Tru64 5.1B (at least) does have /dev/urandom.