Organizing a Software QA department

I’ve got a tough one. I’ve been asked to look at the way the company does QA testing with the thought of trying something better. The issues are that we allow too many “simple” errors out the door, we take too long to complete a test cycle, and we don’t effectively use the automated test tools that we purchased. We aren’t horrible at it, but I would agree that we are not the most effective group and it should be possible to do better.

So — I’m looking for suggestions, starting at the highest level.

What is the best organizational structure for a QA group? Should QA be it’s own department that reports to the CIO or should each development department have its own QA group? If the latter, how do you suggest coordinating between groups?