How should I approach a situation where my head of department doesn't want me there? I'm in my first year of a PhD programme in the UK. In this year of the programme we do a few short projects with different supervisors and then choose a supervisor and project for the next 3 years.

My current supervisor is fantastic - I work really well with him and he also thinks highly of me. I am making great progress with my work, everything is going well. Of the ~4 supervisors I've worked with in the past, this experience is by far the best I've had. My supervisor is very keen to have me continue with him for my main project, and I am too. 

The problem lies with the head of my supervisor's department, who also happened to have been the head of my master's programme that I took last year (before becoming head of dept this year).

He taught me for a total of three weeks during that master's. I made a bad first impression in the first week when he called on me in class with a question that I didn't know the answer to and I replied with something silly. The second week I was seriously ill and had permission to be absent, but when I came back in the third week he was angry with me for having missed a week. At the end of that short course he gave me a failing grade. I appealed the grade unsuccessfully.

My supervisor has told me that before I started working with him the head of department "warned" him about me and said "I don't want a person like that in my department".

Now my supervisor, having worked with me for a few months, disagrees completely and doesn't understand why the head said that. But, perhaps unsurprisingly, my supervisor doesn't have a very good relationship with the head of department either. I worry that the head will not take his opinion with much weight.

I'm worried that I won't be allowed to continue in this department with my supervisor, and that even if I am there will be trouble down the line. What can I do?
You shouldn't worry so much about political issues in the department. What is important to you right now is to focus hard on the research and publish in significant journals with your supervisor or collaborators. Hence, in this way you can justify that are a serious student in the department, and you can established connections for you career after graduation the PhD program.