I don't know if these were negatives that were scanned, or if you have a digital camera, but whatever, I certainly would do the following :
1- Don't go back to that place unless you want to ask for a refund
2 - Find an Minilab with a machine instore, the machine should be an Agfa d-Lab, or a Fuji frontier. Both of these machines are the new generation of minilabs which scan the negative and print to normal photo paper using a laser exposure method. The Agfa lab ( I am biased of course ), has very smart picture enhancement qualities, particularly when it comes to underexposed negs, scatches, and contrasty negs...
3- After you 've done this, and have nice photo's in hand, go and rub them in the noses of the unforendly chain, and then demand that refund !
Ps, these labs also print directly from most digital media as well.