That really depends on when they next crawl the site. It shouldn't take long for the changes to be visible - remember though, the cache takes a bit longer to refresh.
were you originally in the index and then got removed? Did you do something dodgy before you got de-indexed? and what do you mean by "SEO'd"? Please provide more specific details of your circumstances.
Keep in mind that Google does not always update the cache date every time they crawl your site, so if you changed the page title, check the title that is listed in the search results to see if it has changed or not.