I have tried this:
SPFolder folder = ...;
folder.Item["Name"] = newName;
folder.Item.Update();
And it behaves mysteriously. If I run it, it throws an exception:
SPException: Cannot complete this action.
HOWEVER, if I stop it in the debugger after the new Name assignment and before the Update(), and look at the properties of folder.Item, then continue, it works every time. It's not a timing thing, I tried stopping it in the debugger without looking at it in the Locals window, but it threw an exception that time.
This question indicates a similar solution but using SystemUpdate(), does that matter? http://stackoverflow.com/questions/3632389/programmatically-changing-name-of-spfolder