I was hoping to use this program for layout work (thats what I thought it was for, if a printer can't use it, what's the point!Why do they have all those brochure templates if they can't be printed, or am I using the wrong type of printer?).
Pages can output CMYK files just fine, which is what most brochures and similar documents would use (many of which, as lo_tech suggests, would be printed digitally). But Pages is simply not a high-end, professional page layout tool suitable for doing more complex things like using Pantone spot colours in separations. That really is the domain of specialized pro products like Quark XPress and Adobe InDesign.
That said, I would think your printer
should be able to do a four-colour separation of the file you've provided. I may not be clear on what their objection is, but it sounds like they simply don't want to produce four plates for the print job, and instead want to only do two. I suppose that's understandable from a cost point of view, but even if the file has a narow colour range, it should still be possible (even if a bit more expensive) to do a CMYK separation.
The other option is as lo_tech suggested, and print it digitally. For short runs this will be cheaper than offset by quite a bit, although offset really benefits from economies of scale, unlike digital printing.
PowerMac G5 Mac OS X (10.4.4)