Just temporarily as a test, put a 220uF (or similar) directly across the Battery and THEN switch the PIC circuit On/Off from that Battery/Cap combination. The Capacitor may well be able to provide a reservoir to overcome the initial current draw which is probably causing a lazy PSU startup. If this works, you can easily construct a pre-charge circuit to charge a capacitor at switch-on and thereafter turn the PIC on a second or so later.