Default [Q] Recovery Won't Boot

Somehow I've messed up my recovery and it won't boot anymore. The phone boots up just fine, but not into recovery mode. When I try and go into recovery mode, the blue text "Recovery Booting" shows, sits for about 5-10 seconds, then boots up the regular system (currently the latest cyanogenmod M6 release).

I've tried flashing different recoveries using Odin 3.09 and 1.85, but both of them fail with "Odin Fail (auth)". On the screen it says "odin secure check recovery failed". I've also tried flashing different recoveries through ROM Manager and GooManager, both of which claim they flashed successfully, but still won't boot into recovery. The phone is still rooted, is there any way I can get a working recovery back??