<edit>
Bah! I typed out this whole long post--which is still very relevant and should be read--and then I realised your problem is very simple. You need to rename your page--the one that you have the include on, not the one you are including (although you can change that one too if you like)--to .php instead of .shtml.
</edit>
I should have noticed this before, but your problem is that you are trying to put a whole other complete page within an already complete page. You have a start and ending body tag and html tag in both documents. This is not needed.
When you are including something, you are not putting a whole other page in, you are merely putting a section of a page in. For example, if this were my page:
<html>
<head>
<title>Hello World!</title>
</head>
<body>
<div>This is some content that might
change frequently and that I want to
include from a seperate file!!</div>
</body>
</html>
Now if I wanted to put that div into the page using some sort of include, I would do the following:
(Main page)
<html>
<head>
<title>Hello World!</title>
</head>
<body>
<?php include "myfile.txt"; ?>
</body>
</html>
(myfile.txt)
<div>This is some content that might
change frequently and that I want to
include from a seperate file!!</div>
Notice how the page that I am including doesn't have a whole other set of <body> and <html> tags? I would assume this is where you are experiencing problems. Hopefully this helps.