I've tried multiple times to flash ClockworkMod recovery onto my unlocked Galaxy Nexus (LTE\CDMA variant "toro" build) device. Each time I can boot into recovery and ClockworkMod displays. However, if I completely reboot my device (boot into Android and then reboot), when I try to run recovery, my phone shows an android with a red exclamation point and refuses to boot. I've tried flashing from both Linux with the fastboot tool as well on the device itself with ROM Manager. ROM Manager reports that ClockworkMod 5.5.0.4 is flashed.
What am I doing wrong?