If the manager was let go for his own bad performance, you may be ok as long as you don't diss him. In some respects just knowing the bad score came from a manager who was not well-thought of can help.
However, you still need to explain it. Above all don't just say that it was the manager's fault. What you had was a personality conflict and you chould have been more pro-active in dealing with it and not letting it get to that point. At the first sign of negative opinion by your boss, you could have sat down in private with him and talked about what you needed to do to improve. Then tried to do what he told you to do to improve. If the conflict was clearly not resolvable after that, you could have tried to move to another part of the company and to another job before getting the poor rating.
What have you learned from this? Well one thing you could have learned is to be pickier about who you want to work for in the future! You could have also learned to pay more attention to the negative messages and to be pro-active in making sure your boss knows what you are doing and how well. You could have learned better ways to deal with a personality conflict. You could have learned that ignoring bad news doesn't make it go away and that you have to pay more attention to what the boss wants vice what you want to do. You could have learned that when the boss tells you that he disagrees with how you do something, then you need to change what you do. You could have learned to gain allies in the corporate world, so that you don't get thrown under the bus at rating time (employees of poorly performing managers rarely get high ratings because their boss doesn't have the political clout to get even when they are doing well).
Luckily for you, this wasn't your last performance rating. You can point to the improvement of your performance ratings as proof that you have better learned to deal with the soft skills as well as the actual technical skills.
