What tools/expertise would be required to produce something like this presentation and how much would you expect it would cost to produce if someone had it storyboarded out?

YouTube - 2008 Latest Edition - Did You Know 3.0 - From Meeting in Rome this Year (http://www.youtube.com/watch?v=jpEnFwiqdx8)

I'm guessing its AfterEffects, Photoshop, and perhaps Illustrator. but I'm not sure.

Looks like you hit it right on the head. Photoshop, After Effects and Illustrator. But I would guess that they used Motion.

Not familiar with "Motion". Is that a program or an effect?

Based on my knowledge, this *can* be created entirely using software like Adobe Flash
animation software, multimedia software | Adobe Flash CS4 Professional (http://www.adobe.com/products/flash/)

OR

Illustrator/Xara Xtreme for the graphics (vector) + Vegas/Premiere etc for the animation part.

Budget wise, low $x,xxx should cover, done by a pro.