I had the same effect with a batch of Reala - in fact some of the "slightly outdated, but cold storage and 100% perfect" junk frequently distributed over the internet.
I do my own C41 processing, and even prolonged or repeated bleaching and fixing could not resolve this problem. It almost cranked my processing routine, because I thought I must have been done something wrong.
I had no such problems with another batch of Reala which I had used some months earlier, nor had I experienced this problem with other Fujis.
The explanation of PE sounds very reasonable. Looks like Reala does not keep very well.