Yellow_Sun - 11:53 pm on Dec 6, 2010 (gmt 0)
You have answered some of your questions; shallow linked, new website, 404 issues, etc.
With newer websites it takes time to get crawled fully and trust needs to be built with Google. Great links will help do a deeper crawl as well, but you will need to have some patience. While Google is doing its thing, I would continue adding new unique quality content and obtaining quality links as much as time allows. Doing so will definitely speed things up, but either way you have a ways to go yet until all pages will get indexed.
Keep working at it and quality over quantity.