Letterman probably swiped that from Youtube, Google Video, or Metacafe. Think Metacafe was where I saw it first.
Right here
Or else the Letterman bit came first, then it was posted online, no timestamp on the OP's link. Oh well.
Either way, you just know Cheney and Rove had their heads in their hands when Bush said that. Then Bush got swatted with a rolled up newspaper afterwards.