Во-первых, поисковые системы не сразу обнаруживают изменения. Чем меньше и малопопулярнее сайт - тем дольше временной лаг. Используйте "Переобход" в панелях вебмастеров. Но в любом случае, средний срок - 1-2 недели.
Во-вторых, кэшированная версия сайта также должна обновиться в самой поисковой системе.
В третьих, поисковые системы могут менять ваш тайтл, если сочтут его слишком спамным и несоответствующим. Гугл делает это регулярно, последний год - практически системно.