Did you get prints too? Did your prints lack the same clarity? If so, then the issue isn't the scan, it is what was the exposure on the negative. If your prints are clear, then they might have scanned them at a certain resolution and then made multiple copies of that scan but in lower resolutions. Any time you interpolate a scan, you throw away or add pixels. Generally you will lose sharpness as a result. I suspect they scanned in a high resolution and then just interpolated it down to the smaller resolutions and saved them. They should have sharpened them before saving.
Also, when you print a scan on your printer, make sure they are printed at 300dpi. What looks good at 72ppi on the screen prints lousy at 300dpi on a printer.
--- "I hear and I forget. I see and I remember. I do and I understand." -Confucius