I had the same thing happen with a pair of Nikes some time back.

On someone's recommendation I had a couple of feet of duct tape tucked in a vest pocket. I carry it wrapped around an old credit card. Makes a pretty flat package and stiff enough to peel easily.