Parece que estás haciendo el ejercicio con menos de 20 páginas o estás usando la variable equivocada para los cálculos... o ambas! 
 
    
Código PHP:
Ver original- // Conviene tener la página actual en una variable 
-     // Si no se especificó en URL, entonces es 1 por default 
-     $page_current = (isset($_GET['page']))-  ?  (- int ) $_GET['page'] : 1;
 
-     // También hay que validar que esté dentro de los límites 
-     if($page_current < 1) { 
-          $page_current = 1; 
-     } 
-     if($page_current > $page) { 
-         $page_current = $page; 
-     } 
-   
-     // Esta es la cantidad máxima de enlaces a mostrar 
-     $max_links = 20; 
-   
-     // Sigo suponiendo que en $page tienes el máximo de páginas 
-     if($page <= $max_links) { 
-           // Si tienes menos enlaces que los que "deseas" mostrar 
-           $inicio = 1; 
-           $fin = $page; 
-     } else { 
-               $inicio = $page_current - round($max_links / 2); 
-               if($inicio < 1) { 
-                     $inicio = 1; 
-               } 
-               $fin = $inicio + $max_links; 
-               if($fin > $page) { 
-                   $fin = $page; // Creo que en $page es donde tienes el máximo de páginas 
-                   $inicio = $fin - $max_links; 
-                   // Verificar si inicio es menor que uno??? 
-               } 
-     } 
-     // Es mejor dejar siempre el número de página intacto 
-     // y calcular el inicio adecuado para los resultados (offset) 
-    $starting = ($page_current * $record_by_page) - $record_by_page;