Dickie

It might be a long shot, but I have noticed that the description tags and keyword tags generated by AIO SEO are not technically compliant, as it closes the tag without a space preceding it…
e.g

<meta name="description" content="content"/>

where it should be

<meta name="description" content="content" />

Now this might not actually affect anything, but who knows…

Or better still, rather than hack the core code…
write a plugin to do it…

Something like this should do the trick, copy all the code and paste into a file called gallerycss.php, make sure you have no white space before or after the php tahs (<? and ?>), upload to your plugins folder and activate. (At your own risk)

<?php
/*
Plugin Name: Move Gallery CSS from body to head
Plugin URI: http://wordpress.org/support/topic/164825?replies=5#post-722329
Description: Removes the Gallery CSS declaration and adds into the head
Author: Dickie
Version: 1.0
Author URI:
*/

function test_gallery_removecss($css)
{
	// Note you still need to return the start div
	return '<div class=\'gallery\'>';
}

function test_gallery_addcss()
{
	// Note this is limited to 3 wide column width only
	echo '<style type=\'text/css\'>
			.gallery {
				margin: auto;
			}
			.gallery-item {
				float: left;
				margin-top: 10px;
				text-align: center;
				width: 33%;
			}
			.gallery img {
				border: 2px solid #cfcfcf;
			}
			.gallery-caption {
				margin-left: 0;
			}
		</style>';
}
add_filter('gallery_style', 'test_gallery_removecss');
add_action('wp_head','test_gallery_addcss');
?>

Note though that using this you would no longer be able to use the column reference in the gallery shortcode, as that is calculated into the CSS code we have just overridden.
(e.g. [gallery columns="4"] ), to do that you need to change the %age width in the css in the plugin.

The navigation thumbnails need to be added to your theme template file, you will find an example in the standard Kubrick theme (Default) in the
image.php file

Just add this code into your theme

<div class="navigation">
	<div class="alignleft"><?php previous_image_link() ?></div>
	<div class="alignright"><?php next_image_link() ?></div>
</div>

Be careful though, as apparently that patch can screw up gallery that previously worked… so we need to find a solution that works for everyone. But as it is, if you are having that problem then this should get you out of a mess for the time being.
I will try to keep you informed as to progress on a full solution

Update:
I have found an SQL error in my error_log file…

[31-Mar-2008 07:27:27] WordPress database error You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near '\"menu_order ASC, ID ASC\" DESC' at line 1 for query SELECT DISTINCT * FROM wp_posts WHERE 1=1 AND post_type = 'attachment' AND wp_posts.post_parent = 10 AND (post_mime_type LIKE 'image/%') GROUP BY wp_posts.ID ORDER BY \"menu_order ASC, ID ASC\" DESC made by get_posts

Will need to look into this a bit more… not sure what is wrong, although it looks like it might be a quotes thing…

Sorry… Ignore