I make a little bit of gear on the side, and I've had good luck with McNett products, both Seam Grip and Aqua Seal. Before that was the tried and true Barge cement. All three will dry out to some degree if washed frequently, especially in a machine. But with careful hand-washing you shouldn't have any major problems.
The trick I've found is to apply it to both surfaces, let it set up, then bond it with pressure. You might have to experiment a bit with your adhesive to get the optimum results. Depending on temp/humidity, you may be looking at 30-45 minutes or more.
Surface prep is also huge, like others have suggested. I will use a rapid evaporating cleaner, like lacquer thinner, to clean and slightly soften the base material. Rubbing it in lightly with scotch brite will give the material more "tooth" to bond with.