Could you please provide two screenshots showing your attempts with the "Replace" and "Replace with regular expression" Actions?
Also, show us a screenshot of some of your existing folders.
Without this information, it will be almost impossible to reproduce the "bug".