When you get that "replace" message you had better believe it. No amount of cleaning will fix it, so don't waste inks. It is a problem with the electronics in the head, rather than a nozzle clog. In Service Mode (which allows head checks under any circumstance) I have gotten perfect check patterns from heads in that condition, but as Canon explained it the heads simply weren't able to interact with the printer controller in ways required for calibrated printing.
Don't know what the time limit is on the warranty, but of the several heads I have replaced on my 8300, all but one were supplied for free via overnight shipping by Canon tech support, which is the best tech support I have ever encountered. 1375 ml is extremely low use, had my first head problem somewhere around 4000 ml. I've had at least one head go over 10,000 ml, but most will go much less.
Somewhere in the Canon dialogue box you can download a lengthy status report as a text file containing error codes and so on, I recommend you do that just before you call tech support since that will save some time for both you and the support guy. In particular there are error codes that track how many spare nozzles are available for automatic swap-out on each head, wish I knew how to read those better. The tech guy should be able to tell you about where the other working head is in terms of remaining life.
What I do now is stock one replacement head, the first one of which I had to buy. If something happens (usually on Friday evening!) I have that head available and will use the Canon supplied replacement head as a stock replacement.
Don't really know what Canon's replacement policies are, but I have indirectly inferred from Canon tech support is that the heads are guaranteed for about 1 trillion dots. I know that helps a lot.
As an extreme long shot, I know some people have cleared head clogs by removing the heads, wiping them down, and then replacing the same head. I think there is an article on the Canon Wiki page about this, and I know someone else for whom this has worked. But I believe you are experiencing another sort of issue, so best practice is probably just to contact tech support.
And I'm still printing for a show that starts on the 9th! Fingers tightly crossed.