MontyBurns-
Grapes are very vigorous, so they need severe pruning. You can even remove up to 80% of a grapevine and still have a healthy vigorous plant. Check sources like your local extension service for information on proper timing and how-to's for your area and grape variety. Late winter/early spring is usually best.

Clematis have different pruning needs depending on the variety. If you know the variety, look it up and follow the pruning instructions. Not knowing the variety or having a tangled overgrown mass, take potluck and treat as Group III clematis: major pruning in late winter/early spring. Just prune down to a nice healthy pair of buds at about 12"-18" above the soil. Remove any deadwood. You may lose flowers this year if your plant is a Group I clematis, but you won't lose your mind pruning a clematis vine entwined with a grape vine ;) Research clematis and grape care on the Vines Forums or google re pinching and tying as new growth commences, if you need to.

In short, I would prune first, then pull the cuttings away from the arbor and fence, next carefully unwind the remaining (short) vine lengths, and then remove the arbor/fence wood. You may want to divide or remove some of the plants if they are too large, diseased, or unhealthy appearing. Shade the clematis roots with mulch or flattish rocks. Keep the plants watered if we have a dry spring; give compost tea and a topdressing of manure and compost when growth begins. Set up the new structure for the vines to grow on. Fasten the new growth to the structure with ties.

There are no doubt many ways of approaching this renovation work--this is but one!

Ginger