Hard to tell from the description, but it sounds like a problem with transparency flattening.
You sent the printer a PDF? Did the PDF look correct on your screen? [Press Quality] PDFs leave transparency live, so any problem with flattening would have happened at the printer, but without a lot more inofrmation, it's not really possible to say this for sure.
What version (including the patch) of ID are you using? Hold down Ctrl on Windows, or Cmd on Mac while selecting About InDesignto get the full version information. And please show us a screen capture of the ID file in that area. You can emebed an image inyour post using the camera icon onthe web page like this:
At the moment i don't have an access to this file, but:
Indesign Trial 5.5
PDF was printed on a regular laser printer and it was ok, i was opening this pdf in an inkscape/adobe reader and it was ok. And yes, i have sent pdf to print house.
Certainly sounds like you need to have a talk with the printer.
Did they show you a proof before running the job?
no, they did not, but for their justification it was urgent job, so there was no time for proof. I am not going to pay them for this screwed print and i am looking here for some support.
I don't know what sort of support you want us to give you. Show them the print from your laser that has the gradient, and see what they say. Without a proof, though, you don't have a lot of bargaining power. If they're honorable, they'll reprint for free, but you should NEVER go to press without a contract proof, and most printers will insist on one, too, for their own protection. This is especially important on a rush job -- it takes less time to catch an error at the proof stage than to reprint the entire job.
I am looking for support, that YOU just gave me! Thank you.