Your guide is probably in a layer or sub-layer that you have locked.
Layers palette (
Window > Layers or f7) and twirl open (click the triangle) all parts you have locked. There's bound to be some
<Guide>s there, one of them your little cyan offender. Unlock it, select it with the
move tool (or you could just 'meatball' it in the
Layers palette) and hit Backspace.