Usually when I compile my kernel I make the initram with...
Usually when I compile my kernel I make the initram with
mkinitramfs -o initrd.img-`uname-r` `uname -r`
(or substitute `uname -r` with the version number you want), I thought that update-initramfs was just used by apt-get when you upgrade some kernel module, and I believe that calling update-initramfs -c just fall back to mkinitramfs.
Maybe it's obvious but are you shure you did update grub (or lilo, or whatever bootloader you use) after you created the new initramfs? initrd.img may be there but grub must have knowledge of it.