Why would you want 100uF on your reset pin (which is MCLR on the PIC if I understand correctly)? It doesn't have to wait that long to start, does it? Something like 100nF should be plenty. And you did bypass the capacitor with 4-10k or so of resistance, didn't you? Doesn't the PIC you're using have some proper power up timer so you don't need the capacitor at all?
Did you rule out software bugs? If you program the software to just output a constant value on each pin, do they remain constant? Try to flash a LED on reset (long enough to be visible) so you can see if the micro is resetting. The micro won't draw a lot of current, so you don't need a lot of decoupling capacitance if your power source is stable, lead length is more important than capacitance (100nF ceramic should be fine, plus some small electrolytics before and after the regulator). Try powering it from a 9V battery to rule out conducted power supply noise. How did you build the circuit, on a solder less breadboard with long wires everywhere? Are there any noise sources like fluorescent lights close by? Try turning these on and off to see if it makes any difference (make the problem go away or trigger it).