That's weird your code does look good. I haven't used get_children myself and the codex suggest that get_post may be easier.
Here is the code that I use on one of my sites:
<ul>
<?php if (have_posts()) : while (have_posts()) : the_post();
$args = array(
'post_type' => 'attachment',
'numberposts' => -1,
'post_status' => null,
'post_parent' => $post->ID
);
$attachments = get_posts($args);
if ($attachments) {
foreach ($attachments as $attachment) {
print "\n";
echo '<li>';
echo wp_get_attachment_image($attachment->ID, 'full');
echo '<p>';
echo apply_filters('the_title', $attachment->post_title);
echo '</p></li>';
}
}
endwhile; endif; ?>
</ul>
It doesn't specify the order either, but it works.. Maybe try using get_post() instead?
Times like this I wish I had more time to learn the ins and out of php and wordPress. :(