Dialogue in ST V suggests that it was a new ship. There is nothing on-screen to suggest otherwise. What Roddenberry said doesn't matter because he had nothing to do with the production of the movies at this point and just liked to make statements like that so nobody would forget he was there.
It doesn't seem all that mysterious. A ship was being built when the 1701 was scuttled. After the destruction of the 1701 it was descided to name the new ship "Enterprise." While ship names are often chosen even before construction is started, it is not uncommon for names to be changed before actual commissioning. In fact, the descision to name her Enterprise may have come at the same time Star Fleet decided to decommission the 1701 before Kirk stole her.
That's another thing. The Enterprise was going to be taken out of service in III, but I always wondered if another Enterprise was on the drawing board. Perhaps the E-B was to originally be its successor, but the E-A was quickly rushed into service?
It's fun to theorize about.
If the Enterprise A was a brand new ship, not a refit and rename of an older ship, then why was it decommissioned after Star Trek 6, a mere 5 years after it was commissioned? It was not that badly damaged.
Also, wasn't the production of Constitution class ships winding down by that point? Why build another Constitution class ship, if only to decomission it in 5 years?