Whenever I am working with a worksheet that has a lot of records (approx
1000) and no formulas Excel seems to slow down when I want to do anything,
even just changing the page breaks or opening a print preview.
I have tried copying it into a new worksheet and restarting Excel and even
the computer but it doesn't work.

This is a problem that I have experienced on Excel 2000 and 2003.