Default Unable to boot to recovery. 4.3

When I try go boot to recovery I get a triangular warning saying I've installed unauthorised software and should bring it to a Verizon store. Rooted, but not unlocked. What causes this, and how do I fix it?