I don't know if you already solved this issue, but anyway I will explain how I got rid of this same issue some time ago.
It looks like Eclipse (I was using Helios) has some problems with the CXF integration (same like it had with Axis before). So, when I got the problem I tried to configure the "overwrite existing files without warnings" as I did with Axis, but that did not work with CXF now.
Then, to recreate your CXF WS project correctly (I agree it is not the most cool way to do) you need to delete the SEI (only if it was autogenerated, like the tutorial you referenced do) and quit the implementation of this Interfase in the WS class, also delete the package where the classes code was generated (*.jaxws) and finally delete the wsdl folder which is inside the WebContent folder. After you do that, then recreate your web services with the changes you did to the WS class.
Ps: I am almost sure that only one of those thing is needed to be deleted (I deleted all these to recreate my test), maybe the wsdl folder, no time to continue testing right now, you tell me.