IfFirst of all, make sure that you got the proper "recovery.img" for your device. Invalid header is not a good message.
Then,if you are able to communicate with an Android phone via adb, you can boot it into recovery mode by command "adb reboot recovery".
What I suggest for your situation is(I assume you don't need fastboot oem unlock):
- Make sure your PC can see your device by the command: "adb devices".
- Boot into fastboot mode by the command: "adb reboot bootloader".
- Flash recovery image to recovery partition: "fastboot flash recovery recovery.img".
- Exit fastboot mode: "fastboot reboot". (Some bootloaders may support fastboot boot recovery.img, I am writing for generic.)
- After exiting fastboot mode, wait for Android to boot, then check if your PC communicates with your device: "adb devices".
- Reboot into recovery mode: "adb reboot recovery".
- Now, the bootloader is expected to load CWM.
In case you need "fastboot oem unlock"(you will see a warning like "partition flashing is not allowed" at 3rd step above, because of verified boot feature.); under Settings->Development Settings, turn on OEM unlock. Then, run below commands:
- adb reboot bootloader
- fastboot oem unlock