Here's the thing. If there isn't sufficient history for your keywords and/or your account, it's probably always going to start high. But that doesn't mean that it's going to STAY high.
Last week I started my own AdWords account for one of my own personal sites. This is the first time I've done this (and I conveniently had a credit to use from a seminar I've taken recently). I've been working with client accounts since AdWords started, but never had one of my own.
Anyway, I uploaded 933 keywords and got really high (for me) minimum bids. I was aiming to get them at 3 to 5 cents each, but all of them started out at 10 to 50 cents, or even higher. Google had no data on my personal account, my site, or my keywords yet, and so assumed the worst.
I set my default CPC to .05, and took my top ten or so keywords that I really felt were most important, and put them at the inflated minimum bid. That meant I had 10 active keywords, and 923 inactive ones. And I set a very small daily budget; only a couple of bucks.
After only a day or two, I noticed that some of my quality scores had already improved to Great; I could lower those minimum bids back down to .05 and .03, and some of my inactives went active automatically. Then I could take the next few important keywords and raise them to their inflated minimum bids - I wasn't risking too much, because I kept the daily budget small.
Anyway, it's been a little over a week now, and out of 933 keywords, I have a little over 500 active at .05 or lower now. 931 of them are at OK or Great; I have two with a QS of Poor. Since the peak time for my website doesn't start until late May or early June, hopefully by then I'll have almost all of them where I want them to be.
The point I am trying to make here is that it isn't necessarily an overnight process anymore - with a new campaign or a new account, and when there's no history for the quality score, it takes time to build it up. You might have to be patient and use a little strategy to get there.
There might be some of this that applies to existing accounts and campaigns as well, but I haven't figured that out yet.