Since you already said that you created a sitemap, yet your still getting comments telling you to create a sitemap! All I have to say is, create a sitemap, LOL
Doing optimization in wrong way won't help. If you are expecting google to index your 1000 pages created in one night, its highly impossible. It will look like a spamming.
Weren't the sitemaps only for 500pages? He has 1000+/- ? I think that backlinks are the solution for your question.