Sorry to hear of your predicament. One advice for you next time: DON'T PAY IF YOU ARE NOT HAPPY. I don't agree with Funksoulava, if the lab has always been using fuji paper in the past, and you have a continuous relationship with them (ie they know you are a photographer and you use them) there is that expectation that the shop maintains a constant quality. THe shop owner was quite wrong not to inform you that he changed paper.
If I were you, I would call CASE - there is a new act that protects helpless customers from people like the ones at the lab. Take in your remainder prints to them and ask them to help you - or at least lodge a complaint.