I had a similarly frustrating experience with multiple phone calls to Delta to get a European pass ticketed, but it did eventually work, and one of the legs was on KLM. I had to call a couple of times to find someone who was capable, and then had to explain the codes that needed to be available for each airline. Q class needs to be available for KLM. I wonder if they can't book the tickets because there is no Q class available for the flights you want.