I don't think it is an old or new issue. Indexing is only a link issue. Have good internal linking and get strong external linking. If you launch a new site or add new pages make sure that Google finds links to this new content. When I launch a new section to my websites I usually add a link to it from my home page. If I launch a new site I do the same.
I have never had a problem with Google indexing a site. This has nothing to do with Sandboxing.