I have some strange HPLC phenomenon and would like your input.

I have developed a method to analyze some porphyrin type of compounds on ACE C8 column using water/methanol/0.1%TFA (TFA in both mobile phase). The method has been used for a couple of years with reasonable separation even though it's been noticed that the column needs to be replaced quite frequently. However, when we ordered a couple of new columns recently, the separation could not be repeated. Instead, very broad peaks had been obtained on the brand new columns. The peak shape was not improved after EDTA wash of the new column. Discussion with column manufacturer didn't reveal any differences between the old column and the new column. As a matter of fact, some of the columns have been packed by the same batch of silica. The side by side comparison has also been performed to rule out any differences in the sample, mobile phases, and instrument configurations.

If "side by side comparison" means you only changed old for new columns, nothing else, than it looks like your method was not robust. Probably you should get rid of the TFA and use a buffer, instead, at a somewhat higher pH (for longer column life).
Are your compounds the acids of mammalian origin? My interest stems from a stability problem we had with protoporphyrin IX.