Could you try renaming the recovery image to be "recovery.img" (no quotes)?
I've been looking at the fastboot source
, if the guys at xda aren't able to come up with anything it may be possible to remove the signature validation code, then recompile fastboot and try with that. But again this would be last resort...
I hope it works out, I'd cry all day if I my Magic died