Page navigation not working

Just in case, here is my code for the index.php

<?php get_header();?>

<div id="skybanner"><h2>Recent Headlines:</h2>
<?php query_posts('showposts=4'); ?>
<?php while (have_posts()) : the_post(); ?>
<li><a href="<?php the_permalink() ?>"><?php the_post_thumbnail(); ?><p class="skylink"><?php the_title(); ?></p></a></li>
<?php endwhile;?>
</div>

		<?php if (have_posts()) : ?>

		<?php while (have_posts()) : the_post(); ?>

		<div class="post" id="post-<?php the_ID(); ?>">

<h2><a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title_attribute(); ?>"><?php the_title(); ?></a> <?php edit_post_link('- Edit Post'); ?></h2>
			<div class="postmetadata-twitter">

<script type="text/javascript">
				tweetmeme_url = '<?php the_permalink(); ?>';
                                tweetmeme_source = 'airandseabattle';
                                tweetmeme_style = 'compact';
			</script>
<script type="text/javascript" src="https://tweetmeme.com/i/scripts/button.js"></script></div>

<div class="postmetadata-top2">

<span class="date-text"><?php the_date('F d, Y'); ?> ( <?php comments_popup_link('No Comments', '1 Comment', '% Comments'); ?> ) - Written by: <?php the_author_posts_link(); ?></span></div>

			<?php the_content('Read more &rsaquo;'); ?>

			<div class="postmetadata-bottom">

Posted in: <strong><?php the_category(', '); ?></strong>&nbsp;&nbsp;&nbsp;|<strong><?php echo '<ul class="addtoany_list">'; if( function_exists('ADDTOANY_SHARE_SAVE_ICONS') ) ADDTOANY_SHARE_SAVE_ICONS( array("html_wrap_open" => "<li>", "html_wrap_close" => "</li>") ); if( function_exists('ADDTOANY_SHARE_SAVE_BUTTON') ) ADDTOANY_SHARE_SAVE_BUTTON( array("html_wrap_open" => "<li>", "html_wrap_close" => "</li>") ); echo '</ul>'; ?></strong>

</div>
		</div>
		<?php endwhile; ?>
		<?php endif; ?>
		<div class="navlink">
			<div class="alignleft"><?php previous_posts_link(); ?></div>
			<div class="alignright"><?php next_posts_link(); ?></div>
		</div>
<?php posts_nav_link ('sep','prelabel','nxtlabel'); ?>
<?php get_footer();?>

why do you need this?

<?php posts_nav_link ('sep','prelabel','nxtlabel'); ?>

i was just playing around with page navigation to see if it would help fix, im removing it now

in index.php, instead of:

<?php query_posts('showposts=4'); ?>

try to use:

<?php
$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
query_posts('showposts=4&paged='.$paged); ?>

@alchymyth That totally worked! Thank you! It fixed the problem with pagination but the “Headlines” along the top change along with the page. Not sure how I can keep that static to the 4 most recent Headlines but I’ll keep trying. If you have any recommendations I’m all ears ??

has anyone created a gawker.com “top headline” style section on their blog? what would be the best way to approach this? im probably doing it wrong at airandseabattle.com

this could work:
(make a backup copy of your working index.php first)

<?php get_header();?>

<div id="skybanner"><h2>Recent Headlines:</h2>
<?php query_posts('showposts=4'); ?>
<?php while (have_posts()) : the_post(); ?>
<li><a href="<?php the_permalink() ?>"><?php the_post_thumbnail(); ?><p class="skylink"><?php the_title(); ?></p></a></li>
<?php endwhile;?>
</div>

<?php
wp_reset_query();
$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
query_posts('showposts=4&paged='.$paged); ?>

	<?php if (have_posts()) : ?>

         <?php while (have_posts()) : the_post(); ?>

i’ll try it out. thanks again!

WORKED. Brilliant!