if you search Google with a search argument like:
"random: nonblocking pool is initialized" slow boot
you will find a lot of similar problems, but I was not able to find a real solution posted yet.
But as some people were happy just going back to Ubuntu 12.04 maybe you could just do that, until you find a real cure. I am not an Ubuntu user, maybe they have some kind of bug tracking system and you can check there if the problem has been reported as it should, and is taken care of. Else you could just file a bug yourself.
In any case I wouldn't bet for a hardware issue as a different Ubuntu version works well on the same machine.