Hi,
I'd guess Klaus's most recent reply is worth considering re breadboards. Apart, and I guess irrelevant here - on breadboards (and finished PCB designs) I always add 0.1uF, 0.1uF, 1uF or 0.1uF, 1uF, 10uF at the (bread)board supply pins and at least 0.1uF and 1uF (+ maybe a 10nF sometimes) on all IC supply pins. Perhaps OTT to some but it works well.
Does putting the MCU/PIC/the IC that has the 4MHz signal on another breadboard make any difference? I guess it won't.