One of the issues with Stuxnet is that in certain cases it will directly modify the PLC firmware and not just user logic. Erasing the CPU memory, including the MMC card, would completely clear out the memory on the S7 controllers and remove the worm.
In case you are not certain how to do this, we have provided the relevant section from the Siemens CPU 31xC and CPU 31x: Installation Manual.
Please remember that you must be certain that the STEP7 project file used to download the program after the memory reset is uninfected, otherwise you start all over again. Stuxnet hid in STEP7 project files it to re-infect the ES when the project file was opened (Special thanks to Joel Langill for help confirming this).