You can't just run checktable on all tables, you need check alloc and check catalog too. Could be that it's one of those phases that's failing checkDB. Can't tell without more info.
CheckDB is Check Alloc, Check Catalog and then Check table on all tables.
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability