https://developer.mozilla.org/en-US/docs/NSS/NSS_3.14_release_notes
~~~
Changes in NSS 3.14

Certificate signatures that make use of the MD5 hash algorithm will now be rejected by default. Support for MD5 may be manually enabled (but is discouraged) by setting the environment variable of "NSS_HASH_ALG_SUPPORT=+MD5" or by using the NSS_SetAlgorithmPolicy function. Note that SSL cipher suites with "MD5" in their names are NOT disabled by this change; those cipher suites use HMAC-MD5, not plain MD5, and are still considered safe.
~~~




Here can see RHEL 6.4 updated system (ie. nss 3.14) fails 
~~~
# rpm -q nss nss-sysinit nss-tools nss-util
nss-3.14.0.0-12.el6.x86_64
nss-sysinit-3.14.0.0-12.el6.x86_64
nss-tools-3.14.0.0-12.el6.x86_64
nss-util-3.14.0.0-2.el6.x86_64

# unset NSS_HASH_ALG_SUPPORT

# yes | /usr/bin/keyutil -c makecert -g 2048 -k /tmp/server.key -s "CN=server.domain.com, O=Example" -v 36 -a -o /tmp/server.crt 2>&1 | tail -n 5
Generating key. This may take a few moments...

(null): bad certificate request
: error -8016
(null): 
~~~



Then with NSS_HASH_ALG_SUPPORT set to include MD5 we have success:
~~~
# export NSS_HASH_ALG_SUPPORT=+MD5
# yes | /usr/bin/keyutil -c makecert -g 2048 -k /tmp/server.key -s "CN=server.domain.com, O=Example" -v 36 -a -o /tmp/server.crt 2>&1 | tail -n 7
output will be written to /tmp/server.crt
Made a key
Opened tmprequest for writing
Created a certificate
Wrote 1682 bytes of encoded data to /tmp/server.key 
Wrote the key to:
/tmp/server.key
~~~






Also with downgrade of nss to 3.13.6 resolves issue
~~~
# yum -y downgrade nss-3.13.6-2.el6_3 nss-sysinit-3.13.6-2.el6_3 nss-tools-3.13.6-2.el6_3 nss-util-3.13.6-1.el6_3

# unset NSS_HASH_ALG_SUPPORT

# yes | /usr/bin/keyutil -c makecert -g 2048 -k /tmp/server.key -s "CN=server.domain.com, O=Example" -v 36 -a -o /tmp/server.crt 2>&1 | tail -n 7
output will be written to /tmp/server.crt
Made a key
Opened tmprequest for writing
Created a certificate
Wrote 1682 bytes of encoded data to /tmp/server.key 
Wrote the key to:
/tmp/server.key
~~~

This Bugzilla has been reviewed by Red Hat and is not planned on being addressed in Red Hat Enterprise Linux 6, and will be closed. If this bug is critical to production systems, please contact your Red Hat support representative and provide sufficient business justification.

For the record: This bug was fixed with the release of updated NSS packages in RHEL 6.5 that reverted the change made in RHEL 6.4.

See the 6.5 Technical Notes -- specifically, the explanation about bz 918136, quoted for convenience:

> With the 3.14 upstream version of the nss package, support for 
> certificate signatures using the MD5 hash algorithm in digital 
> signatures has been disabled by default. However, certain websites 
> still use MD5-based signatures and therefore an attempt to access such 
> a website failed with an error. With this update, MD5 hash algorithm in 
> digital signatures is supported again so that users can connect to the 
> websites using this algorithm as expected. 

( https://access.redhat.com/site/documentation/en-US/Red_Hat_Enterprise_Linux/6/html/6.5_Technical_Notes/nss-and-nspr.html#RHBA-2013-1558 )

The wording is a bit odd (because this doesn't just affect users connecting to websites ...) but I've tested and can confirm that genkey works again in RHEL 6.5 (or simply 6.4 with updated nss packages).