Just posted this in someone else's thread but I'll put it here too. It's the only way that works for me and so far 2 or 3 other people have had success too.
This happened to me so many times when I was first learning how to flash ROMs. This is what worked for me.
Open ROM Manager. Press your phone's menu key, go to settings. Check the option for "erase recovery prior to flashing" or whatever it says exactly. Then go back to the main ROM Manager screen. Go to the top and flash the recovery again. Wait for it to say success. Then tell it to boot into recovery. This time you should succeed in getting to the menu instead of the error message.