OK, I resolved the first issue and I think I have an idea why the 2nd problem is happening.
[1] is because the template includes l_sidebar, r_sidebar and navigation .php files. The original template basically renders the entire page. But since the template works only for the page it is applied to, WordPress renders header, sidebars and navbars for you anyway, so as the result sidebars were generated twice.
[2] I think this is not a Cutline issue but the server issue. Default/original template for sitemap has showposts=1000 in the constructor of WP_Query, but by trial and error I found that any value higher then 45 will crash the page. Conclusion?
a) either the server doesn't have enough memory to render the entire page or
b) a post in the range from 46 and higher has something that makes the loop break.
Here's my final version of the template. Check it out at http://www.MaxiMovieBlog.com/site-map
Note the absence of sidebars and navigation as well as <div id="content_box"> tags.
<?php
/*
Template Name: Sitemap
*/
?>
<?php get_header(); ?>
<div id="content" class="pages">
<?php if (have_posts()) : while (have_posts()) : the_post(); ?>
<h2><?php the_title(); ?></h2>
<div class="entry">
<p>" alt="<?php bloginfo('name'); ?>">Home</p>
<h3>All internal pages:</h3>
<?php wp_list_pages('title_li='); ?>
<h3>Most recent internal blog posts:</h3>
<h3>Monthly archive pages:</h3>
<?php wp_get_archives('type=monthly'); ?>
<h3>Topical archive pages:</h3>
<?php wp_list_categories('title_li=0'); ?>
<h3>Available RSS Feeds:</h3>
</div>
<div class="clear rule"></div>
<?php endwhile; endif; ?>
</div>
<?php get_footer(); ?>
===================================================
So has anyone had the same problem? Do you have more then 100 posts on your blog? How much memory do you have allocated for PHP? I believe I have 40MB allocated to me by the hosting provider.