We narrowed down the problem to this:

When we created a primary key clustered index on one specific table (regardless of columns) we received the error. Our work around was...

Additional Info:

We loaded data into an empty database one table at a time. We narrowed the problem down to one specific table.

Additional Info:

Tried dbcc checkdb, reorg indexes, backup/restore, etc. DTS'd all data to another sql server db - same problem. DTS'd to a Sybase db and no problem. ...