Thanks to Mohammed Sharaf, who passes along this post from Paul Randal’s blog regarding a corruption issue people are running into in SQL Server 2005 SP2.  Here’s the money quote:

The situation is this: a table with a non-unique clustered index (i.e. so a hidden uniquifier column is created), and then rebuilt using DBCC DBREINDEX. Sometimes an incorrect query plan is chosen so the rows in the index get sorted incorrectly. A subsequent DBCC CHECKDB (or DBCC CHECKTABLE) will return errors like:

Msg 2511, Level 16, State 1, Line 1
Table error: Object ID 2073058421, index ID 1, partition ID 72057594044678144, alloc unit ID 72057594048348160 (type In-row data). Keys out of order on page (1:16042), slots 47 and 48.

The workaround is to use the new ALTER INDEX command in 2005 to do the rebuild (remember that DBCC DBREINDEX is deprecated). There's also a hotfix available in CU9 (and the upcoming SP3 I guess). Checkout KB 954734 here for details.

Thanks, Paul and Mohammed, for getting the word out..