This occurs when using computers that require an EFI Firmware Update to use the Lion Recovery feature.
If you are experiencing this issue, Apple Hardware Test is available on the media that came with your computer. See Intel-based Macs: Using Apple Hardware Test for more information.
For more information on Lion Recovery, see OS X Lion: About Lion Recovery.