Ifirst met George Bush at Camp David ... shortly after he took over as President. From our visits to Washington we had got to know Al Gore, the Democratic candidate, and his wife Tipper, reasonably well, so I think it's fair to say that our hearts sank when the result was finally ratified. Bush was, after all, a Republican. In fact, Tony felt very strongly that Gore was playing it wrong and that he should have used Bill [Clinton] more, not distanced himself from him. He seemed not to realise how much goodwill Bill still commanded, and he is one of the great communicators.

We had watched George W on television and felt that he didn't seem comfortable with foreign affairs, yet Tony was determined that they should have a good relationship. Others of our party - notably Alastair [Campbell] and Sally [Morgan] - had a more mixed view. “Let's face it,” I said. “He's probably not looking forward to it much either. He knows we're friends of the Clintons, and he also knows you're a Labour Prime Minister and all the rest of it, so everybody's going to be a bit nervous, everybody's going to want to try and get along.”

The fact that the encounter was in the semi-rustic setting of Camp David was indicative, in a way, of the difference between the two men. With Bill Clinton we'd been entertained lavishly with a formal banquet at the White House, with Stevie Wonder and Elton John. The Clintons never really got going till late, whereas the Bushes were tucked up in bed by ten. That first night with the Bushes, we had an early dinner. The meal over, the President said: “Why don't we all watch a movie?” So we did. He got all the new releases on DVD, he explained, and that night we watched Meet the Parents with Robert de Niro.

This was the famous occasion when George made the remark about him and Tony having Colgate toothpaste in common. In fact, they got on remarkably well. George is actually a very funny, charming man with a quirky sense of humour. The reason he gets a bad press, he says, is “because I talk Texan”. Bill Clinton was also from the South, but while Clinton may talk Southern, he doesn't think Southern, whereas Bush thinks Texan.

There had certainly been a slight sense of anxiety before the meeting, but by the time we left the general consensus was that “he's a guy we can easily get on with”. We may not agree in terms of domestic politics but in terms of international diplomacy that is largely irrelevant. And the special relationship is precisely why, when the Republicans took over, there was never any question that we wouldn't do everything we could to get on well with them, too.

[A month later, the Bushes visited the Blairs at Chequers.] Like us, the Bushes are very family-orientated. Laura was an only child brought up by her mother, and she married into this big family, with everyone having loads of children. But she and George only had the twins, one named for her mother and one for his: Jenna and Barbara. That evening at Chequers was very much a family affair and, as well as our children, James Dove, Euan's schoolfriend, was there. He had always been interested in politics and, perhaps because he was present, the conversation was more wide- ranging than it might have been if it had just been us. Certainly I couldn't see me or Tony raising the question of capital punishment, but that's exactly what one of the kids did. So there we were discussing the death penalty: in one corner an American President who believed in it; in the other a human rights lawyer who very definitely did not. I stated my view: that it was inherently wrong and that if you make a mistake you can't put it right.

George just said, “Well, that's not the way it is in America. We take the eye-for-an-eye-view.”

But it was completely and utterly good-hearted. The way George handled those kids and their questions, I thought all credit to him. And I know that both James and Euan were pleasantly surprised that he could actually string an argument together and didn't turn into some sort of raging bigot. I often say that I must be the only person on the Left whom George Bush gets to socialise with. But no one can say - at least not me - that he doesn't have a sense of humour.

Laura is a very warm, genuine person whom I liked the moment I met her, and someone I immediately felt completely comfortable talking with. It was clear that we had common ground; like me, she was interested in other women and women's issues generally. When we met we would talk about our families and about literature, because we share a love of books. We had more of a women-friends' relationship than I had had with Hillary. With Hillary our conversations were more ideas-based, and of course we had our politics in common. To a degree, when she and I first met I was a little in awe. As Bill's wife, she had already been the First Lady for a number of years and was experienced in the job. But when Laura and I met we were much more on an equal footing, and have remained so.

Explore Books

• Book Extracts

• Book Reviews

• Books Group

Times Recommends

• The Gone-Away World by Nick Harkaway
• Burning is too good for them
• Strange Fruit: Why Both Sides Are Wrong in the Race Debate by Kenan Malik