Try this:

In template.php, replace:

echo '<div id="vote_counter">'. $votes.'</div><br>';

..with:

echo '<div id="vote_counter" class="vote_counter-' . $post->ID . '">'. $votes.'</div><br>';

In voteme.js, replace:

jQuery("#vote_counter").html(response.vote_count);

..with:

jQuery(".vote_counter-" + post_id).html(response.vote_count);

You should also declare post_id and nonce as local variables; i.e.:

var post_id = $(this).attr("data-post_id"),
  nonce = $(this).attr("data-nonce");

Hope that helps.

[EDIT] Provided better replacements.

Try this:

In template.php, replace:

echo '<div id="vote_counter">'. $votes.'</div><br>';

..with:

echo '<div id="vote_counter-' . $post->ID . '" class="vote_counter">'. $votes.'</div><br>';

In voteme.js, replace:

jQuery("#vote_counter").html(response.vote_count);

..with:

jQuery("#vote_counter-" + post_id).html(response.vote_count);

You should also declare post_id and nonce as local variables; i.e.:

var post_id = $(this).attr("data-post_id"),
  nonce = $(this).attr("data-nonce");

Hope that helps.