Sory if this is a bit of necroposting.

Flash is the ticket. You can make a map like the one in the link using simple timeline animations without getting into actionscript (The flash coding language). I don't think you would need any other software beyond a vector editor (The drawing software in flash drives me absolutely nuts!).

I've been toying with the idea of doing somethings similar myself, but with using animated icons (shields and banners, etc) rather than solid blocks of color. That's a few projects away, however.