This is a known bug with WordPress 3.0, and there is a bug fix logged in the Trac database, found here:
http://core.trac.wordpress.org/ticket/13471
As a temporary and immediate fix on my site, we made a very small change to the post-template.php file in the wp-includes directory.
You need to replace line 622, which currently looks like this:
$output .= '<a href="' . trailingslashit(get_permalink()) . user_trailingslashit($i, 'single_paged') . '">';
With:
$output .= '</a><a href="' . trailingslashit(get_permalink()) . user_trailingslashit('?page=' . $i, 'single_paged') . '">';
THEN, also replace line 636 in exactly the same way, replacing:
$output .= '</a><a href="' . trailingslashit(get_permalink()) . user_trailingslashit($i, 'single_paged') . '">';
With:
$output .= '</a><a href="' . trailingslashit(get_permalink()) . user_trailingslashit('?page=' . $i, 'single_paged') . '">';
It should work fine after this fix.