Nick, I was just doing some testing on my system... same problem that you described.
I found this bug report posted on another forum:
Seems to be related to mkinitrd... Long story short, I suspected that perhaps the kernel and mkinitrd get updated in the wrong order with yum, so what I did to fix was remove the latest kernel with:
yum remove kernel-2.6.14-1.1644_FC4
yum update OR
yum install kernel-2.6.14-1.1644_FC4
(to grab the latest kernel again)
Hope this at least gives you a clue (wasn't sure if you're custom compiling?)