Is ice-encrusted frozen shrimp ok to eat?
This is how shrimp is frozen for transit and sale. The packaging should have a weight that includes the ice aswell as the shrimp, and a weight that is shrimp only weight: The weight after they have completely thawed. 

There will also be a size grading. No of shrimp per lb or per KG based on whether they are
HOSO Head On Shell On
HLSO Headless Shell On or 
Peeled
Break down here

The ice coating prevents freezer burn to the shrimp, so they'll be juicy when you defrost them rather than dry and hard! If the have freezer burn they'll be a opaque white discolouration on the surface. They're still OK eat like this - they're desecated / dried - they're just really tough.

Having said all this I am assuming that the packaging they're in in undamaged, before I say that they should be fine!