Some users need extra time to get comfortable with the concept of managing files with metadata, rather than the detailed folder hierarchy structure we tend to have a love/hate relationship with.
SharePoint has added a document library view setting to show all items in the library without folders. It leaves all files intact, regardless of how many folders deep they are, and simply shows every file in the library as if they are all on the root level.
As a Change Management recommendation, you should consider creating a view that shows all the important metadata columns, and removes folders. Introduce the view to users when you're rolling out the service. Some will adopt it as their default right-away.
Once you're through the "interim" phase of moving data and adding metadata, you can switch the default view for everyone to the metadata only view.