The CTO said to come talk to him before you start looking elsewhere and he'll find a solution. What you wrote doesn't mean you have promised him to let him know that you're leaving, and in fact you aren't. After all, if you haven't accepted another offer, you're not leaving, right? What you tell the CTO is that you're unhappy about the situation and why, and try to come up with a solution together.
Either the CTO can get you a satisfactory solution or he can't. If the CTO can get you a solution but isn't going to unless you say you're leaving, take that as a no. You want to present yourself as loyal unless and until you have a signed offer elsewhere.
Never tell anyone you're leaving as a negotiating tactic. If you can only get a good deal by threatening to leave, you're still marked as the one who was willing to leave, and one that the company has already made a concession for. That's not a good position to be in. Your colleague may have things work out, or he may have it bite him later. You're female, and unfortunately that means you've got to be more cautious.