The oldest bridge in Rome, the Ponte Sant'Angelo, which links the Vatican and the City of Rome, was the first one Christo and Jeanne-Claude proposed to wrap, in 1967. At the same time, they also had their first proposal for a wrapped museum, the Galleria Nazionale. They failed to get permission also.
Although Christo made some collages using the Sydney Harbor Bridge when he and Jeanne-Claude were in Australia in 1969 to realize the Wrapped Coast, they never officially asked permission to wrap the bridge.
Three years later, the artists considered to wrap the Pont Alexandre III in Paris but soon abandonned the idea, because the towerless one-arch bridge offered a profile which Christo and Jeanne-Claude considered too skinny, and it also was not really used by pedestrians.
Finally, in 1975, Christo and Jeanne-Claude decided to wrap the Pont-Neuf, the oldest bridge in Paris. The project was realized ten years later.