Take them to a shoe cobblers. They have the correct glue for shoes that is strong as hell and waterproof. Plus he'll do a better job of preparing the surface and clamping it :?
A friend of mine on another forum uses Shoe Goo for this kind of thing (he actually glues quad roller skate plates to boots with it to save the weight of bolts!)