It's nothing to do with SEO it's to do with how often the search engines are crawling your site and indexing it, the fact that you are submitting a new site map makes it readily available to the search engines rather than having to spider all over your site to find it.
How busy/popular is your site?
EDIT: scratch that, i just checked, your site is brand new, you've got a lot of work ahead of you in order to get indexed like you're expecting