It looks from this like several million will be the correct figure.
I heard that only about 3 million bitcoin addresses are used. I would say that the number of addresses > number of users.
Myself, I have used dozens of addresses, and don't consider to be a heavy user of addresses.
It may be that many people are holding their coins on MtGox. Perhaps because they don't feel comfortable holding them themselves.
Here's the magazine where I saw the interview:
