Just to clarify... You are trying to do this OTA and not thru the Desktop Manager correct? It has been my experience that emails that have been moved into folders within the email client prior to the user receiving their BB will not be synced to the new device. I was dealing with Lotus Domino/Notes but I believe it is the same on Exchange as well. All the folders themselves will be created on the device, but not the items within those folders. But any new items that are moved into those folders will sync just fine.
Does that make sense?
Now I also seem to remember a really messy workaround for this but it had to deal with dropping the BES SQL db, creating/importing a new db, then importing all the old info into the new db but it seems hardly worth the trouble.