They should not have to remove shoes, no. Here is the TSA guidance for "Persons with Prosthetic Devices, Casts, Body Braces":
http://www.tsa.gov/travelers/airtrav...rial_1370.shtm.
Security Officers will need to see and touch your prosthetic device, cast or support brace as part of the screening process. We will not ask nor require you to remove your prosthetic device(s), cast, or support brace. During the screening process, please do not remove or offer to remove your prosthetic device(s).
Also read further down the page for "Orthopedic Shoes, Support Appliances, and Other Exterior Medical Devices".