[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.