1. separate words into more adgroups (no more than 5-10 words per adgroup
2. write mote targeted ads and run 2 per adgroup to determine which one has higher CTR and then test another one
3. check geo-targeting may be? sometimes it helps too
4. do more homework (what competitors are doing); make sure your ads scream for attention and are well-written (great title that matches main kws from that adgroup, benefit in 1st line, feature in 2nd desription line (or something that yr clients would Hate (i.e. "Never get fat again!") if you sell some weight-loss stuff, for example..
5. Really expand on negative kw list if there are any phrase or broad-matched keywords - that's just as important as having a good list of keywords
6. Heck, I would even get a new domain and create an SEO-friendly site, on a fast server and start copying the best perfoming keyword/ad combinations to a new ac.. (hm).. well, I mean, peel and stick, right?
They say it's possible to get to top positions in any market, although it would take alooot of time to do that. With all the ad split-testing and so on.. You can't expect new results using old methods - gotta keep on digging. There's a free book out there called adwords domination or smth like that (it's really free) and it quickly describes how to launch new campaign in competitive markets, it deals with position preference too, worth a look, I will be using some tactics from it soon. Sorry if it violates any TOS, no self-promotion here, really. HTH :)