Problem paginating a subquery on a post

Have you tried adding the paged parameter to your args for WP_Query?

$args=array(
   'tag__in' => $tag_ids,
   'post__not_in' => array($post->ID),
   'posts_per_page'=>10, // Number of related posts to display.
   'caller_get_posts'=>1,
   'paged' => $paged
);