Digital BW, The Print

I recently had a local photo store do some scanning for me of some B&W 
35mm negatives.  I was very disappointed with the results.  Areas in 
shadow, the details of which are visible in the negatives, were 
complete lost in a sea of black.  No way could I get Photoshop to bring 
out the details. The negatives were scanned by a high-end Nikon scanner 
(so I was told) and show up as 4,000 pixels per inch.  I asked if the 
scanning couldn't be adjusted to quiet down the blacks, and the answer 
was yes, but that this store didn't do that kind of custom work, and 
didn't want to get into same.  I was also told that the grain in the 
film made it very difficult to get a good scan.  I was given a full 
refund, which I hadn't asked for, as some of the scans were somewhat 
o.k.  So, I don't know.  Maybe I should try a different shop?  Would I 
be able to do better if I did my own scanning?  (I don't want to put a 
lot of money into a machine which I wouldn't be using all that much).  
Or is the scanning of negatives bound to result in a vastly inferior 
image?

Norm