One simple way is to put the PIC PWM through the PIC comparator, and use the comparator as an inverter. That gives you complimentary PWMs, and the comparator can be switched off etc when you need both LEDs to be off.
You could also use one of the PICs that has complimentary PWM outputs built in, I think the 18F1330 is one that is fairly small pinout?
Since you only have two channels you also have the option of just manually generating the PWMs in an interrupt etc, LEDs only need about 100Hz to be flicker free so a crude low-freq manual PWM will work fine.