Wow.. its almost exactly the problem I just had on a fairly new iPF6400. I was going to do a write up but haven't had a chance yet. Here is what I can tell you.
Since you are missing half a channel, the manual states that this could be anything from a printhead issue, a carriage issue, or a main board issue (I had the 2f43 error which I think is similar to yours). I would print a nozzle check from the service menu just to see if its any different. I had an entire half missing as well, but is started out with columns missing, not the whole thing, which for me pointed to some electrical problem.
Anyway, so first the printhead was replaced, no luck. Then the entire carriage unit was replaced, no luck. Then the main board was replaced, no luck. Now here is the thing. If the mainboard was initially bad, it may have fried the new carriage unit. And once the new mainboard was put in, the new fried carriage unit more than likely killed the new main board. So at this point, more parts have gone into this printer than what its worth (good thing its under warranty), but since there weren't any replacements available (have you noticed how every 6400 is out of stock!!), they had to try and fix it some more by installing a new main board, a new carriage unit, and 2 new printheads all at the same time, which finally worked. (although there is a bit of squeak now and I know this printer wont last as long given that its had its guts replaced several times now)
My case is a bit different because the printer was 2 months old, so it more than likely looks like an initial faulty main board. The tech told me that they do routinely replace carriage units and that fixes the problem on printers that have been printing for a few years. But, there is no guarantee, and these parts aren't cheap. If a new printhead doesn't fix the problem, and I"m not even sure if I would look into that myself since its $450, I can't see pumping money into it. Funnily enough, the tech also told me about a guy who had an 8400 delivered dead on arrival and thinks because it was shipped really far, it was the move that killed it.
Anyway, so perhaps I'm jaded a bit now, but throwing money at printers when you really don't know what the problem is, especially when its electrical, is perhaps a waste of money in the end. Shame the rebate on a new 8400 is over now.
EDIT: I see that you put new heads into it already... ouch. So for sure you're looking at either a carriage unit or a main board now. The problem of course now is what if the printhead you just put in fries the new carriage unit if you put one in. With a new carriage unit, I think new printheads are a good idea based on what I've heard but this of course just goes on and on.