What to do when advisor does not want to work together? I have been a PhD student for 3 years (UK), and recently there has been severe trouble with the relationship with my primary advisor.

I had been struggling on a problem, for quite some time, with only very little advice or feedback aside from vague responses, and decided to try a related problem to see what could be done. There was quite a lot of success, and interesting developments, so I sent the early progress through and got encouraging feedback. So I continued down this track, and was clear to ask, "do you think this is publishable? what do I need to do in order to make this material publishable?" and so on. I got encouragement, so I continued and we built up a paper together and worked towards completing the thesis.

Now very shortly before my submission, he has told me that he recalls this was already done and so much time has been wasted as we cannot use this material. Now my shock was when I find out he was the first author of said research, with a prior PhD student doing this as part of his thesis.

I was absolutely furious (and bewildered) but I will be very clear, I made no negative comment. I went for a long walk and then took the day to think about what to do now.

I tried to ask what other work I could do, could I collaborate on other research he had going on, but got only a vague refusal. I asked for advice on how to proceed from here but got only vague suggestions. So I did what I felt was my only option and mentioned these issues to the panel because important things were going to be postponed. I made it very clear I had no personal issues with him and did not want to assign any form of blame, but that I needed some real help in a path to get some research progressing which I wasn't getting.

The next day he went on a furious rant which involved him calling me lazy in many different ways and telling me to go and work with someone else, that I cannot continue working with him.

At this point, I have only one member of the panel who is willing to work with me, but I have a primary supervisor who is very clear about not wanting any kind of working relationship with me, at least for the time being (which considering the time pressure I face as a student, means effectively that it is over).

What are my options here? I really feel that I did everything by the book, and I see this behaviour as a serious failure in supervision. I just don't know how a previous student's thesis gets re-researched. I certainly cannot rely on a reference from him to start a new PhD, and I don't know if I can continue when the relationship is this bad.
Since you want to go forward, rather than quit, you have only a few options. One is to find a way to get everyone, including yourself, calmed down and focused on the future. The other is to find a different advisor locally or at another university. 

I don't think it is unusual to work on a problem for a while and have it end up with nothing. I've done that and so have many others. However, your advisor should have been more aware of the situation if the work had previously been done. But your literature search should also have turned up a hint of that, at least. 

Maybe someone at your university can set up a "soothing the waters" meeting in which you all come to an understanding of the way forward for you. Focus on the future, not the past. If there is blame about the past, then it is likely shared. It is also normal for people to be upset, and your advisor may be acting badly because s/he is embarrassed about misleading you. 

You probably need to have that meeting even if you want to move to another university so as to make it possible to get good recommendations. Nothing good will come from acting out of anger or in the presence of the anger of others.