There's a product put out by Selleys here in NZ and Australia called "All Plastics". It's a two-stage process, with each surface primed with a felt pen (don't know what's in it) and then bonded with something like cyanoacrylate gel (again, don't know exactly what it is).
I've done head-swaps and other conversions with all sorts of soft plastic figures using this stuff, and it hasn't let me down yet. I can wave a figure around, holding on to it's newly-glued head, and it won't let go.
I expect the same thing is available elsewhere in the world, though probably under another name.
As for priming soft minis, I've had good results from Rustoleum aerosol primers — there's one that specifically states on the label that it's intended for plastics as well as metal.