Who makes the little promo videos that startups typically have?

Sandwich Video make some of the most well-known, though far from all of them. http://sandwichvideo.com/

They don't necessarily have to come from a company. We hired a freelance animator to create ours which can be seen on Kuhcoon.com. The point of these videos is to explain your product in a way that is easy enough for users of all ages to understand. They are super effective, but can be costly. Luckily I am personal friends with the animator so we got a good deal, but from research I've done these animations typically cost around $300-$500 for every 15 seconds.

Check out:

http://www.revolution-productions.com/portfolio/

Checkout http://fiver.com/ People are loving to do such videos fro $5. I have never tried any of them myself.

If you want to do it yourself, 2 sites (from the same underlying company) are: onetruemedia.com and spotmixer.com

http://www.epipheostudios.com/ have had some big clients, including Facebook, Google, Yelp, Microsoft

The thing you are paying for most of the time is for someone to beat the shit out of your story to make sure it's as succinct and compelling as possible -- while being 100% jargon free. Whoever you hire, you want to make sure you get that out of the deal if you are paying $$.

You can see examples of videos our team has done along those lines over at http://whatnowexactly.com/

And to answer the style question - there are probably 10 good companies in the U.S. that do these sorts of videos and we all know one another ;)

How much should one reasonably expect to pay for a well made 60s product video?

inDinero, the Fridge, AnyBot and the iconic (every time I fly Virgin) HipMunk video were all done by GrumoMedia[1].

http://grumomedia.com/