Однозначно дело в истории с доменом от предыдущего владельца. Я им тоже писал не раз по поводу этого и всегда получал стандартные отписки, что мол проблема уже в существующем сайте, хотя сайт был белый и пушистый.
Была история с сайтом на домене с "историей". Тут, на мой взгляд, имеет значение, какая была история. :)
Я свой сайт долго пытался загнать в индекс. И уник контент писал, и тематику менял, и что только не делал. 4 месяца в яше только главная висела. Платоны стандартные отписки писали. В общем, забил я на этот сайт. Подождал, пока с гугла мой уникальный контент "отвалится". Перенес весь контент на новый домен. Причем, шаблон взял абсолютно тот же, что и был. И через 2 недели - все страницы в Яше. :)