UPDATEApparently recoloring these requires some srs voodoo/ritual/raindance shiz.

I found that if you open the _HL_CEP_FireplaceXX.package file before recoloring, then SimPE will load the required textures just fine. You MUST open the CEP file for the specific fireplace you want to recolor first. This puts it in the cache for SimPE which is letting the OW read the files. I have no idea why it's doing this, and I have no idea how to get SimPE to read this properly otherwise.
I find this acceptable since a) How often are you going to recolor this? lol
(unless your kate... :-) ) b) With drag/drop it takes 2 seconds to drag the CEP file into the SimPE window and then you can start OW without even closing the CEP file, and c) I've tried going back several versions of SimPE and they all behave the same way for me, and I've tried the files in multiple places and separating the files in various ways. Nothing else works, I've tried asking Inge about SimPE but she remembers nothing as she has moved on to TS3.
NOTE: My tests were done with SimPE v 0.72.1 for AL with the M&G update.
SimPE v 0.72.1 and
M&G Update- Files are Updated - Can't say for sure what I may/may not have changed so get the new ones
So please try recoloring like this, it's worked for me over and over all day yesterday. Yes I know it's a pain.