I had the same problem, different counts from sp_spaceused versus select count(*)

So I tried sp_spaceused with @updateusage = 'True', and I also ran DBCC UPDATEUSAGE for the table.

And the numbers never varied. My only thought is possibly a corrupt table.

Luckily I have little need for record counts from large tables :^)...