This only addresses the second part of your question, how to know what size of CPLD you need for a design:
Typically the amount of logic you can fit in a CPLD is limited by either the number of flip-flops (or other latches) or the number of I/O's in your design. Generally you get one flip-flop per macrocell, and something less than one I/O pin per macrocell. The basic design allows one I/O per macrocell, but often some of the I/O's on the die are not bonded out due to the limited number of pins in a given package.
So, for your design, you have 14 flip-flops for your two counters and you're good. Normally I wouldn't recommend using programmable logic for the phase comparator in your design but at 17.5 MHz and if you aren't very particular about how exactly you match up the input and output phase, you should be able to get away with it. You'll still need an external VCO and filter circuit. So with a 32-macrocell CPLD you should have no problem fitting the digital elements from this design with some room left over for other glue logic you might need.
That said, generally a design for such a small CPLD is so simple that you can code it up in an hour or so and use the vendor's design tool to be sure it fits before moving forward. All of the CPLD vendors I know of offer free versions of their design tools that cover almost all sizes of CPLD.
Finally, though the estimate of 1 flip-flop per macrocell is accurate for classical CPLDs like the one you linked to, some vendors (Altera & Lattice come to mind) have taken a major architectural excursion in their newest CPLD families. These devices are more like mini-FPGAs than like the classical CPLD, and I'm not sure that they calculate their "macrocell-equivalent" sizes according to this formula. The new devices are likely to have more flip-flops per device, but not allow very wide fan-ins to the logic in each cell.
As for the other part of your question, is this a good use for a CPLD, that's a tougher question. I don't see any reason not to use one, but maybe someone will come up with a clever way to build this circuit at lower cost / less board space / lower power, or whatever.
No, if the nMos is on, that means it conducts. If it conducts, it is a low resistance (ideally zero). That creates a conductive path to ground, bringing the output to that potential.
Think of the two devices as being resistors controlled by voltage. If the upper resistor is shorted, the output is 5V. If the lower one shorted, the output is at ground.
Best Answer
Since no answer so far (and one has a score above 20!) actually mentions FPGAs, I'll add the answer I think you are looking for. You can't invert a clock on an FPGA with logic for various reasons:
Skew. The inversion is not instantaneous, so there would be a transitional time with both clocks matching. You probably don't want this.
Architecture. FPGA's logic elements have dedicated clock input lines that are independent of the data lines. To route from data to clock nets involves connections that are suboptimal.
If you are trying to get an inverted clock inside the IC, you'll have to use one of the architecture's native clock modules.
If you are trying to drive an output with an inverted clock, the major vendors all have DDR logic that you can use to send the "data" of a continuous
010101at "double data rate" which is actually the clock inverted. The dedicated circuits will handle any corrections needed. This lets you avoid using global clock resources for the inverted clock and also gives you a way to invert the clock in the field with a control register.