Prior to changeset:7561 the gallery html looked pretty much like this when you put [gallery] in a post containing 2 photos:
<p>
<style type='text/css'>
<!-- the stylesheet -->
</style>
<!-- see gallery_shortcode() in wp-includes/media.php -->
<div class='gallery'><dl class='gallery-item'>
<dt class='gallery-icon'>
<!-- the thumbnail -->
</dt></dl><dl class='gallery-item'>
<dt class='gallery-icon'>
<!-- the thumbnail -->
</dt></dl>
<br style='clear: both;' >
</div>
</p>
Note that the whole thing is enclosed in <p></p> and everything is nested correctly.
However now the html looks like this:
<style type='text/css'>
<!-- the stylesheet -->
</style>
<p> <!-- see gallery_shortcode() in wp-includes/media.php --></p>
<div class='gallery'>
<dl class='gallery-item'>
<dt class='gallery-icon'>
<!-- the thumbnail -->
</dt>
</dl>
<dl class='gallery-item'>
<dt class='gallery-icon'>
<!-- the thumbnail -->
</dt>
</dl>
<p> <br style='clear: both;' >
</div>
Now the bug (after all that!) is that the opening <p> on the 2nd from bottom line is never closed.