a few thoughts but no real hard advice.
Tannin staining is reasonably common in cedar but this might be some kind of oily wood extractive.
You dont state whether you have used water based acrylic (wash brushes in water) or oil based paints (wash out brushes in mineral turps.)
if water based then i think its tannin staining.
i'm thinking an oxalic acid cleaner might be useful. Ask at your paint store and do some online research first. no guarantees
oxalic acid is usually used to restore old timber decking.
The aussie wood working site i post at sometimes has some real cluey blokes i'd reccoment asking there. maybe a photo or two of the bare wood and stained paint.
http://www.woodworkforums.com/