Digital BW, The Print

Hi,
I am using my 24x36 BW negatives as a basis for my prints. The 
scanner is a Canoscan FS4000US and I am scanning at 4000 dpi in 
Photoshop. The scans are very good with the exception of the skies 
(with- or without clouds, light or heavy) which are broken up and 
mottled. Can anybody tell me the reasons for this? And how to avoid 
it? The negatives are carefully processed and show no discernible 
graininess. I would very much appreciate any help on this problem.
John