It sounds like one or more of your print heads may be overheating and turning off. The HP 260 (nearly the same printer just a newer name and firmware) actually warns you when stuff like this happens or is about to happen, but I've heard of other 25500 owners not getting notifications about this.
Since there are two of each print heads you may have replaced the wrong head(s). My suggestion is to run color boars on the far left of your print and watch for which color is dropping out. You can tell which head it is by the position of the dropout. If it looks forward or back you during a single pass then you can look at the position of the print head that corresponds to the lost color.
Ultimately you need to identify and replace the bad print head to cure the problem but there are things you can do to extend the lifespan of your heads and or extend the use of a marginal head.
1. Set the lowest possible drying temperature for your media. For a lot of profiles they the dryer is set to 55c. This is very hot and I have found 45c to work for most of my media without loss of detail or over saturation of ink.
2. Don't use "High Ink Bi-Directional" for long jobs. This really makes the heads work hard and I have lost many heads before learning this. The prints are great but you need to factor in new heads if running this way.
3. Increase your inter-pass delay - This will allow the print heads to cool down (although slightly) during each pass. I am on the fence about this when you are running anything smaller than 60" media though since the heads delay at both ends.
4. Enable extra print head cleaning. This is the most effective solution albeit the most costly relative changing settings but less expensive than dropping heads and the loss of expensive materials/time
5. Make sure your printer has access to cool air flow. Even if you have your dryer temp set low it will be hard to hold if the room has poor ventilation for cooling.
6. Break up the long jobs. I use Flexi to print my jobs and so I can send all or portions of a tiled job vs exporting and loading jobs into a rip and I have found that when I send long jobs (Van wraps...) all at once that I have higher failure rate with heads due to the extended time the print heads are under the dryer. After I began breaking long jobs into quarters or thirds I have found a dramatic increase in head life. I have several heads now pushing 7000 ml without any incidences. Prior to this I would lose heads around the 3500-4500 and when running High Ink I was losing them before their warranty expired (1000ml)!
The print heads are cheap compared to other wide format printers and most HP latex users rightly consider them consumables, but for me I like to get the most out of what I have and I'm sure many share the same sentiment.
Anyway, best of luck and I hope other's offer their input too so we can all learn.