Do you have robots.txt file? If you don't have it, create one. It helps a lot for me. AFTER you've created one, then submit your sitemap.
I would be wary of the sitemap idea... There is a lot of information floating around out there, some of it is really negative and if true, would not be wise to submit.
If you want the bots to have full access to all linked pages, keep the robots.txt file empty. These things just take time. Concentrate on optimizing your content and gaining links, the rest is just waiting. Good luck