Why does the shrimp stick to the shells? I made some NoLa bbq shrimp last night, using the same recipe I’ve used countless times; the only difference is that, on Alton Brown’s advice, I brined the shrimp in a salt/sugar bath for 15 minutes before I cooked them. The dish was delicious, especially since I found some heads-on shrimp, but the shrimp were inexplicably hard to peel. The flesh and the peel were bonded, and it was like peeling a cooked egg when it just goes wrong.

Could this be because of the species of shrimp, or how long it’s been sitting in the display case, or did I make an error in cooking?
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.