Every estimate I've seen of the total number of bitcoin users is completely arbitrary. I think 625,000 is probably low.
If it's any consolation, The Bank of England estimated in
their bitcoin report, that there is currently 1.6m wallets addresses with a balance over .001btc. That's easy to verify on the blockchain. If a study can link the number of wallets addresses per user, then we might be on to something. How to find a random sample of bitcoin users to query may prove challenging, but that's why some firms specialize in things like this. Personally I'm interested in the answer, and I think a lot of prospective bitcoin startups would like to know as well.