Broken pagination

I see a few issues that are probably contributing to your issue:

1. Only ever use query_posts() to modify the primary Loop.
2. The caller_get_posts parameter has been deprecated, in favor of ignore_sticky_posts
3. The $wp_query variable is a defined global. Using it outside of its intended use may cause unintended circumstances.

So, first, you need to determine which is your primary Loop. I will assume this to be the second loop.

Second, come up with a unique, descriptive name for your secondary loop (i.e. your first loop), such as $most_recent_sticky_post.

That should leave you with:

<?php
// Get IDs of sticky posts
$sticky = get_option('sticky_posts');
// first loop to display only my single, 
// MOST RECENT sticky post
$most_recent_sticky_post = new WP_Query( array( 
    // Only sticky posts
    'post__in' => $sticky, 
    // Treat them as sticky posts
    'ignore_sticky_posts' => 0, 
    // Order by ID
    'orderby' => ID, 
    // Get only the one most recent
    'showposts' => 1
) );
while ( $most_recent_sticky_post->have_posts() ) : $most_recent_sticky_post->the_post(); ?>
    <!-- loop code -->
<?php endwhile; wp_reset_query(); ?>

// second loop to display every other post, 
// excluding sticky posts
<?php 
query_posts( array( 
    // exclude all sticky posts
    'post__not_in' => get_option( 'sticky_posts' ) 
) );  
if (have_posts()) : while (have_posts()) : the_post(); ?>
    <!-- loop code -->
<?php endif; wp_reset_query(); ?>

Now, since you’re no longer stomping on $wp_query, your pagination should work properly.

Edit

Okay, other things:

1. The showposts parameter is also deprecated. Use post_per_page instead.
2. Let’s try doing a merge of query variables for your primary loop.

e.g.:

// Define custom query args
$custom_query_args = array( 
    // exclude all sticky posts
    'post__not_in' => get_option( 'sticky_posts' ) 
);  
// globalize $wp_query
global $wp_query;
// Merge custom args with default query args
$merged_query_args = array_merge( $wp_query->query, $custom_query_args );
// process the query
query_posts( $merged_query_args );

I don’t know that this will make a difference, but I prefer to modify the default query using this method.

1. If that still doesn’t work, then force query_posts() to remember that it’s supposed to use paging. Add 'paged' => get_query_var('paged') to your $custom_query_args array:

e.g.

  // Define custom query args
  $custom_query_args = array( 
      // exclude all sticky posts
      'post__not_in' => get_option( 'sticky_posts' ),
      // don't forget to paginate!
      'paged' => get_query_var('paged')
  );  

Where does that get us?