Typically, this problem occurs after upgrading from Lr1/2 to Lr3. If you have updated then worth noting that Lr3 needs to update all of your previews in any case. So, it may be just as easy to trash the existing lrdata file and rebuild the preview from scratch.
Also, what file formats are you scanning (i.e. raw, PSD, TIFF, JPEG).