Why NM depends on || ( sys-libs/e2fsprogs-libs <sys-fs/e2fsprogs-1.41.0 )? I can't find any mentions of libss, ss.h, libcom_err, com_err.h and ss_err.h, or compile_et and mk_cmds.
It's likely to be leftover from the time before libuuid was provided by util-linux.
Looks fixed in networkmanager-0.9.6.0