Why does the shrimp stick to the shells?
This is most likely caused by the sugar in the brine you used. There must have some sugar left on the shrimp (especially between the shrimp and the shell), even if just a bit.

When you grilled your shrimp, the high temperature of your barbecue caused the sugar to get caramelized and delicious, but also very sticky. It more or less "glued" the shells to the meat of the shrimp as they cooled to eating temperature.  

You could prevent this next time by peeling the shrimp pre-cooking, but be sure to oil the grate well to prevent them from sticking to the grill and to watch carefully that they don't burn or overcook.