Comment 3 for bug 1256486

I just had this happen when I had insufficient disk space on /boot. That doesn't seem to be your problem. However, I have also had a similar problem when there was enough disk space, but the file system had reached the limit for the maximum number of files allowed -- try looking into that. My solution was deleting old kernel files.