@Johnc,

If you need accuarate numbers then go for count(*). If approximate stuff wud do then use sp_spaceused/SP_ROWCOUNT provided in the article.

Probably your Update stats took a sample scan. Try,

Update statistics tablename with fullscan.

In case if you need to understand statistics, please read two excellent articles

written by the great Gail Shaw 🙂

http://sqlinthewild.co.za/index.php/2008/11/04/what-are-statistics-and-why-do-we-need-them/

http://sqlinthewild.co.za/index.php/2008/11/13/identifying-inaccurate-statistics/