I don't know this for sure but I had similar problems when I first started doing designs for print - OK this was CMYK but the same problems arose - I'd have something looking great but when it came back it was flat as you like - After speaking to a few printers and searching forums etc, it looked the best thing to do was to go into the colour preferences of
PS and switch them off completely
I had a nightmare when I first started doing print but since switching the colour prefs off, everything comes out smashing - literally go into colour settings and set to "colour management off" - then whatever you save is exactly how windows previews it as well - I'm sure unless your printers are using the same colour space as you, they will either ditch your colour profile or use their own
Hope that works
James