Android - Can't connect to the device with ADB when it's in recovery mode

WARNING: fastboot oem unlock completely wipes your data!

adb is not available in the bootloader, try using fastboot instead

for a quick and dirty rundown of flashing your device with a new image using fastboot:

adb reboot bootloader
use fastboot devices to verify your device is visible, if not, you're probably running windows, and you have to install some funky drivers. if you don't see 'unlocked' at the bottom of the screen, use the command fastboot oem unlock then just:
fastboot flash boot boot.img
fastboot flash system system.img
fastboot flash userdata userdata.img
fastboot flash recovery recovery.img

If you feel super confident you could just:
adb reboot bootloader && fastboot oem unlock && fastboot flash boot boot.img && fastboot flash system system.img && fastboot flash userdata userdata.img && fastboot flash recovery recovery.img && fastboot reboot

PS You should only use the flash commands if the referenced files are present, if not you may or may not brick your phone (haven't tried flashing a non-existent file to the device yet)

Warning: Unlocking bootloader wipes off data in your phone.

Stock recovery doesn't come with ADB access.

Try a recent version of ClockworkMod recovery for your device (the older versions don't all have ADB support)

You will need to flash the recovery on using fastboot (see @MishaP's answer)