Many SEO's, when just starting to analyze a site for search engine friendliness, will look for Frames as one of the first things that could signal a problem. Often, the immediate diagnosis is "search engines cannot index content within frames." The two aspirin perscribed are site rebuild and a dose of SEO.
In many cases, this is the most simple of problems and the rebuild will "fix things." A thread over at High Rankings Forum starts with a member asking about their framed site, and how it could actually be ranking at Yahoo, MSN, and even Google?
Some good discussion is following at High Rankings Forum.
Another discussion on this topic has been going on at Search Engine Watch Forums.