Shouldn't the cleaned URL be '*/page/2' instead of '*/2'?

Here is some code changes that will achieve this. I use node/page-2 format because I think it is a bit cleaner. There's still an issue with the code below where if you have a node alias named node/page-2-is-the-greatest, then node?page=2 will be displayed, but at least it is a start.

First, a change to the hook_init()

/**
 * Implementation of hook_init(). 
*/
function cleanpager_init() {
  if (cleanpager_check_match()) {
    if (variable_get('cleanpager_use_seo_links', '') == 1) {
      drupal_add_js(drupal_get_path('module','cleanpager') .'/cleanpager.js');
    }
    $url_array = explode('/',$_GET['q']);
    $page = end($url_array);
    array_pop($url_array);
    
   $page_array = explode('page-',$page);
   if (is_numeric($page_array[1])) {
      $_GET['page'] = $page_array[1];
      $_GET['q'] = implode('/',$url_array);
    }
  }
}

and then a change to cleanpager_theme_pager_link() (which is around line 155 after you change the hook_init function!)

  if (isset($new_page) && $cleanpage && $new_page > 0) {
    return l($text, $cleanpage .'/page-'. $new_page, array('attributes' => $attributes));
  }

As I've already mentioned, there's still some issues in the way this code works. It could be cleaner, and possibly the "page-" could be made a customizable admin setting - but it is a starting point.

I have implemented this functionality in the latest release: 6.x-1.0-alpha3

Note that the urls are created as page/2 and not page-2 as the above fix suggested (mainly because that is what the client requested). There is a setting on the settings page to turn this off and keep the old functionality.