Stand your ground and renegotiate!
If I may reiterate my comments on the original post, at this point you may only have what you agreed to in writing to back you up. However, you can also point out that there was never any knowledge, or statement in writing, of a rebrand in the original contract and use that as leverage to renegotiate (I'm guessing this was a surprise to you or else you wouldn't have asked the question). The client needs to understand that this is indeed a completely separate job from the original and new terms need to be outlined before the design process begins. If anything you can lean on the very recent experience with this client and point out that you have to protect yourself, and time, from any more surprises.
The client should also know that you're not at their beckoning call and that all of that time in which they put you on hold, could have been time devoted to another client. Bottom line is this is a completely new assignment that is going to require your time to solve and you should be compensated for that time and expertise.
If you're unsure how to approach the client, it could be helpful to frame the discussion as a problem solving issue. In this case, the client had a problem (needed logo A for brand A), you solved the problem with your original design and they decided not to go that direction. In fact, they changed direction completely so now they have an entirely new problem that needs solving (logo B for brand B). They can either pay you to do it (a known variable) or go elsewhere and still have to pay a designer to do the new work (an unknown variable).
Something to include on future contracts:
Cancellation / Kill Fees
A “kill fee” is a fee paid by the client to the artist when the client
does not use the artwork. “Kill fee” is a general term that covers two
types of payments: a cancellation fee, and a rejection fee.
Cancellation Fee: A cancellation fee should be paid when the artwork
satisfies the client’s stated requirements, but the client decides,
for reasons outside the artist’s control, not to use it.
Artists generally negotiate the kill fee as a percentage of the
agreed-upon fee for the finished piece. We have seen a wide range of
kill fees, from 20 to 100 percent, usually depending on the stage of
completion of the artwork at the time the project is killed.
Graphic Artists Guild Contract Glossary