I think that Toby Stephens looks just a little young, though he is starting to get the right look. Sean Pertwee...looks the right age, but I am not sure he's got the right look (and believe me, I would be all for the son of Jon Pertwee playing Vimes otherwise).
Hugh Laurie would be an excellent choice. Had you asked me before House came on, I would have told you to bugger off. But House showed his ability to play an excellent dramatic role that is acerbic and misanthropic. Only downside? Doesn't look like he could chase somebody down or beat the crap out of someone.
How about Christopher Eccleston? Not too old, still looks capable of physicality, and can do that sort of cynical and world-weary outlook.