I'm using qTranslate plugin to maintain several languages on my blog and I found out that WP-Paginate produces pagination links without 'localized' part. For example:
Default language page 2 URL: http://some.site/page/2/
English language page 2 URL should be: http://some.site/en/page/2/
This is just an example, qTranslate could generate different form URLs for alternate languages, but this does not matter for WP-Paginate plugin, all author needs to do is to add following code at the end of wp-paginate.php:
if(function_exists('qtrans_convertURL')) : add_filter('get_pagenum_link', 'qtrans_convertURL'); endif;
If qTranslate is used then all the page links in alternate language will have proper localization part, if not - nothing will change.
I've added this code to wp-paginate.php on my site and it works like a charm.