Have you set up the applications to be set to specific Desktops? If you right click an application in the Dock and go to options, It will allow you to Assign the application to the current Desktop or all desktops. If they aren't defined, it might be that when you restart they just default on the first Desktop.
A possibility? I'm not too sure, I haven't had this specific problem, but I don't really use to many different desktops at once.