Get a second opinion. This could be a novice inspector being overly conservative. Do not count on the Hydro facility doing a thorough visual inspection after the hydrostatic test. Many things can easily fall through the cracks (haha! no pun intended) when a Hydro facility is doing a large volume of cylinders every day.
If the cylinder inside is a rubber or plastic coating it will not be worthwile (or effectively possible) to remove it by using solvent, whipping, tubling, or an act of god. Once the manufacturer put that stuff on, its not coming off! If you do go ahead with an attempt to remove this coating it may cost you as much as just buying an aluminum cylinder that you wont be running into these issues with.
A dive shop employee (with a current PSI cylinder inspector certificate) DOES have the authority to "condemn" a cylinder to warn others of a potential danger that could be caused by pressurizing the cylinder. However, due to personal property laws they cannot make the cylinder unable to hold pressure. So, they can stamp out the numbers on the crown, but they cannot drill a hole in the cylinder or damage the threads.
Again, just get a second opinion.