Originally Posted by wige

One thing I have seen Google claim is that they do put some weight on what pages the webmaster thinks are important. This is determined based on internal pagerank (how you link internally), where pages are located in the directory structure, how documents are linked from the home page, how pages are listed on the sitemap, etc. This information is used to some extent to determine what the web master thinks are the most important things about the site, and to determine relevance to different keywords and queries. This may have some impact on what search terms your site shows up for.

Unfortunately, when a large portion of your site goes away due to a redesign or a redirect issue, Google may recalculate what pages it thinks are considered the most important. Although Google has said time and time again that this factor does not determine rankings, I suspect it does have an influence when calculating the relevance score of a domain. As Google scans your content, it will see many potential topics that your site is about. However, it has to figure out what the main topics of your site are, which is based on internal and external factors. So, up to now Google has seen that your site is about "cheap web hosting". Now that your internal link structure changed due to some pages becoming unavailable, even though the "cheap web hosting" page still exists, Google may see that page as being less important, and "budget web hosting" as more important, and changed your rankings accordingly.

It is difficult then to guess what will happen as Google continues processing the pages as they return to the index. It is possible that Google will see your internal structure as being restored and your rankings will come back. It is also possible that Google will continue looking at your site as being about "budget web hosting" and the new links as supporting that phrase.