Wayne,

>We dropped the clustered indexes and added them back - this has fixed the problem.

This is a clear sign that your table was highly fragmented. FWIW if the table has many indexes you should drop the non-clustered indexes first and then the clustered. Otherwise SQL will be reconstructing all the non-clustered indexes which will be invalidated as soon as you rebuild the clustered index.

You might examine the nature of the clustered index, if it's on a column that isn't an identity PK then a highly inserted table will fragment very quickly. For example an address table with it's clustered index on zipcode will end up horribly fragmented as more or less randomly ordered records by zipcode are inserted.