Cyanoacrylate should have no problem holding Polystyrene together. It may be the mold release agent that's resisting it. If that's the case, just leave 'em in soapy water for 10 minutes, then try again. Acrylonitrile Butadeine Styrene, ABS, the plastic Lego uses, has a different release agent that doesn't resist Cyanoacrylate or Acrylic, Lacquer, or Enamel-based paints, thus, out-of-the-box gluing. (Or, painting, if you mean expensive Japanese toys made of ABS plastic)
ABS is a good bit more expensive than PS, but it holds its shape better. It, unfortunately, suffers from much faster yellowing than PS, though.