Here's what I just found doing a search on yahoo:
Many types of glue are acceptable for attaching rhinestones or crystals, except (1) the isocyanate glues (e.g., instant adhesives), (2) any glue containing acetone, and (3) hot glue. There are several brands of glue that are specifically formulated for bonding rhinestones or crystals to fabric. Our recommended adhesives & glue product line includes Beacon Gem-Tac, E-6000, Devcon epoxies, and Aleene's.
Now that I read this, the glue I saw at Michael's was Gem-Tac.