Churchill's career was a real paradox. For large segments of his career, he was reviled by almost everyone - just look at his treatment in the First World War. His wartime tenure at the Admiralty was not entirely successful, but he became the scapegoat for every failure & was drummed out of office. He seemed of have the tag of being a young upstart attached to him (he had previously been Lloyd George's sidekick in the new Liberalism before the war), & so I think so many people wanted to smack down the upstart. By the 1930s, his career was in tatters & seemed without future. Yet almost no one remembers that anymore. His role in the Second World War is the central memory of Churchill (who even remembers that he came back to the Premiership in the 1950s?). I think that is one of the keys: Churchill is remembered for the Second World War, & practically nothing else. And Britain won that war. Yes, British arms may not have been constantly crowned with glory and triumph, but at the end, they won, going the distance against the nastiest & toughest enemy the British had ever faced. Victory has a tendency to wipe away the stains on anyone's reputation (look at Abraham Lincoln or FDR).
Something else to remember is the record of post-war Britain. You mentioned that Churchill lost the Empire, but that is not really true. While academics can pinpoint the start of the decline at some point in the distant past, to the public, the British Empire still appeared to be very much a going concern in 1945. It was only in the years and decades later than it became apparent that the Empire would be lost and that Britain would sink to become a second-rate power. India was not lost on Churchill's watch, the African & Caribbean colonies were not lost on his watch, the economic decline did not become apparent until after he was gone. It is not insignificant that the Suez Crisis happened a year after he retired. Churchill left the public scene before the worst of the decline had occurred.
Also, Dark Knight made an important observation. By his death, Churchill had become a symbol of a glorious and proud age that was clearly in the past and not to be revived. He had come to symbolize all the greatness that Britain had once been, and would not be again. The importance of symbols is not to be underestimated.
Finally, also don't underestimate the importance of 1940. People often forget just how dark that summer was. I would suggest taking a look at John Lukac's "Five Days in May." It describes a brief period after the fall of France had become apparent but before the BEF was rescued from the beaches when there was a push by some politicians to replace Churchill with Halifax & use the still-neutral Mussolini as an intermediary with Hitler to negotiate a peace. This was a legitmate attempt, and the role of Churchill in suppressing it cannot be overstated. The fact that the war continued past the fall of Paris can be attributed mainly to Churchill himself. That, in and of itself, warrants the fond remembrance of Churchill.