You shouldn't have any issues playing back sessions from a previous iteration of your website when using Fullstory. We store the HTML content of each page in real-time (when the user is on the page). A few minutes after a page finishes (i.e. user navigates to a new page or 30 minutes of inactivity elapses), we fetch and snapshot all of the page's referenced resources (images and css). This ensures that old sessions will continue to play back correctly even if your site changes.
If it has been a while and you're still seeing your old design, check out this article for some tips.