Considerable research and countless hours of "throw away" ideas needs to go into these designs and the price quoted in these examples also includes the design and replacement of all marketing materials, signs, boxes, etc, etc with the new logo. Big time agencies are probably going to bill around $250 - $500 per hour. You have dozens and dozens of people working on these projects and good ideas generally take a lot of time.
From experience it is difficult to create a logo (with a visual standards manaul, letterhead, and business cards) for a small company (under 50 employees) in under 100 hours with minimal revisions from the client.