If your site not indexed yet (new site) than you can submit it to G. Usually I tweet the link of the site and G will indexed it sooner.
I dont think is so important to submit your site to Google. Be sure your seo is done right, create a sitemap and submit it through G Webmaster Tools, then start link building
Have you tried it again? I think it should work now, and just like everyone said creating a sitemap on webmaster tool. Good luck