In this economy there are a number of contractors who are jacking up their prices to cover costs since jobs are few and far between. There seems to be a mentality that when things are slow they need to raise rates instead of lowering profit margins. Sounds like that's what your original contractor was trying to do.
On the other hand, customers don't realize that material prices have not dropped in the same manner as home values so they think that new buildings should drop the same amount as the short sale across the street. My wife sees that a lot when people are looking to build new homes. They will come in and say that the foreclosure across the street is selling for $x per square foot so you should be able to build me a new home for that price, why are you more expensive?
Sounds like you've gotten a better quote with the second guy, but before doing anything, check his references, talk to other customers, and above all make sure he's licensed, insured and that all of his sub-contractors can provide proof of workman's compensation insurance. The first one that doesn't have it and wipes out on your property and you could be in for a real costly garage.