I would recommend getting rid of frames, because the of search engine problems such as yours plus some accessibility issues with text-only browsers, some hand-held devices, etc.
You can emulate some of the frame functionality via the use of includes (server-side or PHP) for the common data on each page, using CSS to position and lay out each section of the page.