I managed to do this on Mediawiki 1.22.2 patching includes/specials/SpecialLonelypages.php like this:
--- SpecialLonelypages.php.bk 2014-12-11 12:32:41.317347781 +0100 +++ SpecialLonelypages.php 2014-12-11 12:38:09.453218165 +0100 @@ -52,7 +52,7 @@ return array( 'tables' => array( 'page', 'pagelinks', - 'templatelinks' + 'templatelinks', 'categorylinks' ), 'fields' => array( 'namespace' => 'page_namespace', @@ -63,7 +63,8 @@ 'pl_namespace IS NULL', 'page_namespace' => MWNamespace::getContentNamespaces(), 'page_is_redirect' => 0, - 'tl_namespace IS NULL' + 'tl_namespace IS NULL', + 'cl_from IS NULL' ), 'join_conds' => array( 'pagelinks' => array( @@ -77,7 +78,13 @@ 'tl_namespace = page_namespace', 'tl_title = page_title' ) + ), + 'categorylinks' => array( + 'LEFT JOIN', array( + 'cl_from = page_id' + ) ) + ) ); }