It sounds like reasonable plan, but I have never done it so I don't know if you will have any troubles. I can't think of anything that would prevent that from working. It will mean broken urls in google for a while until they re-index your new url structure. After making that change I might review the urls in url manager and make sure none of them have the previous folder name segment (they shouldn't but I would check in case any do). I'd also check every url in the menu 1 by 1 after the change to verify that all pages work.
One tip, once you move the db to a new server, delete any rows that exist in mp_TaskQueue and mp_IdexingQueue as unfinished tasks from the previous server can cause errors.
Hope it helps,
Joe