Determining the number of clusters using property testing algorithm
First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp.org/p/06/relative/ and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - its well known, but i dont know a ref for that). Secondly, relative approximation sample in this case, guarantees that if the sample fails, then $k$ is too small. So, do exponential search for the right value of $k$, specifically, start with $k_i = 2^i$, and let $R_i$ be the the $i$th sample of size $n_i = O( \frac{kd \log k}{\epsilon} \log \frac{i}{\epsilon} )$ (the $i$ is not a typo).

Let $\alpha$ be the minimum $i$ for which the sample succeeds using the black box. Now, use brute force (on the sample) to find the minimum $k\leq k_\alpha$ for which the sample works. And this is your desired $k$. You need to carefully account for the probability of success, but thats why the $i$ is there - its one of these standard geometric summation stuff. 

The $i$ can be avoided -- indeed, the probability that $\alpha$ is bigger by $\Delta$ than its correct value is smaller than $2^{-\Delta}$. If you do that, then the sample you are going to use is of the right size with good probability. That is, if the minimum $k$ for which you can cover more than $(1-\epsilon)n$ of the points is $\kappa$, then the sample the algorithm uses is $O\left( \frac{\kappa d \log \kappa}{\epsilon} \log \frac{1}{\epsilon} \right)$.

There is some added fuzzyness in the answer of this algorithm. The returned answer $\kappa$ is the minimum such that any value of $k &lt; \kappa$, is say $(1-\epsilon/2)$-far from from being k-clustered. I assume this is OK. 

In practice you would do something different. Hmm. Something to think about....