Let's take a look at how FP's include file function works. Unlike server side includes or PHP which process includes on the server at the time of request, Frontpage processes the includes when you save the changed page -- all of the other pages on which the page is included are rewritten to reflect the change. When a request is made, that page is served without any other processing by the server.
Now, what it sounds like is that you're FTPing the changed include file and not using the FP publishing routine. In that case, while the new page is on the server, the other pages haven't been rewritten with the new information.
The easiest way to fix this is to use FP's routine to publish the site. It will automatically make the necessary rewrites.
If you have to use FTP you can do as you did and upload the page, but then you have to go back to Frontpage and open the live website. When open, choose Tools >> Recalculate Hyperlinks. That will run through the pages and update any changes.