When you say yellow plug, what do you mean? The larger yellow power cable? Hmmm, you didn't mention if you power filtered the head unit - have you tried that?
If you do mean the yellow power cable, I suppose it's entirely possible that this could be the source of your problem. Is your HU wired directly to the battery or are you taking a feed off something else (e.g. the existing HU power cable on your loom)? It sounds like the only thing you haven't changed in the equation is your HU and power filtering of the head unit.
I'd take the power filter off your amp and stick it on the HU to see if that will make any difference. Also, if you've got a spare HU lying around (lol, who hasn't), have you tried swapping that back in to see if it works okay?
Also, another thing to try is to buy an inline RCA filter (Dick Smith, Tandy, Altronics, Jaycar sell them). It can muddy out the sound a bit, but its worth it just to see if that's your problem or not. I missed where you live, but if your in Perth, I actually have one I'm not using.
Here's a link:
http://tinyurl.com/ylk2bh