This year's FOCS paper seems relevant.
"Settling the Polynomial Learnability of Mixtures of Gaussians"
Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians.
Edit 10/25: Suresh has a nice summary of the two papers that appeared on this problem here http://geomblog.blogspot.com/2010/10/focs-day-1-clustering.html