I got bitten more than once with device rooting recently with My Samsung Galaxy S4 and Nexus 7 (2013) and Nexus 10. The latter made me think that something is amiss and my recovery mode was botched. So I went looking just to stumble upon:

fastboot erase recovery
fastboot erase system -w
fastboot erase boot
# Download latest twrp/cwm recovery
# Check md5sum
fastboot flash recovery nameofrecovery.img