General question on dbms_stats
For the most part, the primary impact is that the stats gather faster. For the vast majority of cases it produces equally good stats, but does it way faster. There are a few edge cases where you can end up with inferior stats from an approximated NDV. But for the vast majority of datasets it's a superior method due to greatly reduced computational intensity.

To compensate for the problem of occasionally inferior stats, you can manually increase the sample size of the stats gather job to increase its accuracy.

If you want to know how it works in great detail, here is a white paper by a subject expert:

http://jonathanlewis.files.wordpress.com/2011/12/one-pass-distinct-sampling.pdf