Can you download from ROM Manager from Play Store and accomplish the same? It should allow you to download a recovery of our choice, or let you know you already have a Recovery in place. But I also believe it is the ROM you install that makes the phone boot to recovery, so you may need to start recovery manually until you successfully install a ROM.
Sent from my TouchPad using xda app-developers app
Android devices: Samsung Galaxy S III running BoneStock 3.4 (retired phone: HTC Thunderbolt running InfectedROM NuSense Eternity); HP TouchPad running OaT CM10.1