I had the same problem, but here's what happened.
I edited inittab to boot to runlevel 3 for other reasons.
Logged in as root, did some stuff...then having already removed kernel-x.3-29.fc9...and headers. I did a yum update as root from runlevel 3 and all was good.
No errors...postcript ran without problems initrd.x.img was created and grub.conf was updated.
Rebooted into new kernel and all was good.
Maybe worth a try...if you haven't already fixed it...I assume you probably have.