I would second the vote for the Conti GP 4 Seasons, done 3000+ miles of commuting on them over the past year, and not had any problems. They have worn a bit over the summer, but nothing major. You can even see where nasty things have tried to puncture, but only got through the rubber layer, I think this is reassuring...
It's amazing someone's great tyre is another cyclists downfall, I had conti GP 4 seasons...
BTW can anyone point me to the cheapest online retailer so that I can buy some Marathon plus 700x25c?
I've heard that but I borrowed one and done thousand + miles on it over winter 2011 (in all conditions) and found it a very grippy tyre; I could be wrong but I think people who report that they are skittish may be running them too hard. I cant comment on changing tube because it never p'tured for meI steer clear of gators not a fan. Not great in the wet and also a sod to change tube