Okay, I doubt this will happen often, but...
I had a character, she was Night Elf Rouge called Kybrook. I got her to level 5 using the guide, then bailed out on her, deleted her and started a Night Elf Druid, also named Kybrook. This may be the key, having the same name. The guide loaded up as if I was still the Rouge with all the steps she completed, not the ones the Druid did (which at that point were none). Even clicking Reset didn't set the guide back. No way to manually un-check completed steps either.
Ideally guide should see this is a new character with the same name, even if the same race and class and reset appropriately.

I honestly don't think there is any way to fix this. It's simply in the way Blizzard saves your variables. You need to delete that character's saved variables folder when you delete the character and make one with the same name on the same server - there's not really anything we can do to fix this :( Unless one of the other programmers knows a way?

Though, I suppose if the guide notices the character is level 1 with zero xp then it could reset the character's database. I can do that.

I was about to come back and note that I noticed a couple other plug-ins didn't seem to notice. So I suspected it was a WoW thing itself. I did delete her WTF file which let it reset.
I would think it would be a fairly rare occurrence though so not a high priority.

On second thought, I really don't think I can fix this. Because it sounds like the completed quest database itself is getting flubbed up - it's supposed to be replaced every time you log in with whatever Blizz says it should be.

Your best bet in cases such as this is to simply delete the WTF files for whatever addon is misbehaving.

I am going to close this, since I don't think I can do anything about it and it's not likely to come up often.