FWIW, "cedar" mulch is not even made out of cedar (Cedrus species). It is often made from Eastern red "cedar" - Juniperus virginian - or Western red "cedar" - Thuja plicata. Kinda hard to regulate anything that isn't even made in any degree from what it is labeled!!

To their defense, the companies bagging and selling 'cedar' mulch are only labeling it in the common terminology that most of the gardening world applies to 'cedar'.

Just like anything else, if you're unhappy with the product, take it back, complain and ask for your money back. Make a specific complaint that it is not as advertised and appears to have painted wood and pressboard in it. I would also complain at the corporate level on their website, so it doesn't just stop at the store manager level. Because what they will likely do is throw out the bag you brought back, refund your money and forget about it.

BTW, I am not sure it is OK for them to include painted wood - even if it does not have lead in it. And if there is any obviously treated wood, that gives me pause. I am not sure how EPA looks at this, or your state's env. agency, but it may not be considered clean material for reuse. It may be regulated as a waste and should not be used for mulch.

...and why is the debris always BLUE?

I've found this stuff in bags from Maxway before, too. The bag was extremely heavy and was labeled "professional potting soil." It was nothing but shredded wood with a lot of blue paint among the giant pieces, some other bits of trash, like clearly distinguishable food wrappers and other not-wood stuff. Sounds a lot like your "cedar mulch."

What concerns me is where these come from, and who painted them, with what.

Anyway, I suspect damaged or scrap pallets are being shredded for mulch and potting mixes, and that's where the blue comes from.

The article from Pallet Enterprise magazine (linked below) also says CHEP has a close relationship with Wal-mart

Here in MO they make a lot of pallets out of oak, sad to say. The oak forests in the southern half of the state are logged quite a bit, and the knotty stuff goes to pallet factories. Truckloads of pallets come north out of the Ozarks. They are definitely not treated, just fresh red and white oak.

I'd be interested in more information about this if you have a different experience in your area.

I learn something new here all the time, and I did not know that Methyl bromide is used for pallet treatment, but it is. According to Wiki,

"Bromomethane is the only fumigant allowed (heat treatment is only other option) under ISPM 15 regulations when exporting solid wood packaging (forklift pallets, crates, bracing) to ISPM 15 compliant countries."

ISPM being the intl standard for 'phytosanitation' which I assume prevents the spread of plant diseases.

It's a gas, and I wouldn't expect it to stick around much after doing its work. Although it is toxic. It's also a powerful ozone depleter, so use is going down, but it's still used on pallets.

So far I don't see anything here that would be a risk with respect to mulch.