alla fine mi ci son messo.. non era complicato, ma mi ci sono intricato pure io con la veriabili varie.. divisioni e moltiplicazioni.. poi col sonno che c'ho oggi mi si intrecciavano gli occhi! 
Dovrebbe funzionare come vuoi tu... ho fatto un minimo di test... ma per il sonno di cui sopra non garantisco niente. L?unico problema credo sia quando l'utente modifica il valore in query string e ne mette no che non è multiplo di 15 (nel tuo caso)... i numeri delle pagine vengono fuori con la virgola... 
Però si sistema anche quello, arrotondando con floor credo... ma al momento mi si intrecciano gli occhi.. casomai ti dico meglio dopo
Codice PHP:
function paging($query,$x_pag=10,$num_links=5)
{
//conteggio i record presenti
$resource = mysql_query($query);
$righe = mysql_num_rows($resource);
if ($righe == 0){ return false; }
//calcolo il numero di pagine necessarie per visualizzare i dati
$numpages = floor($righe/$x_pag);
//ottengo il numero di pagina, se manca lo imposto ad 0
$pag = isset($_GET['pag'])? $_GET['pag'] : 0;
//imposto il primo estremo del limit
//appendo il limit alla query originaria
$query .= " LIMIT $pag,$x_pag";
//gesisco la propagazione della query string
$querystring = '';
foreach($_GET as $k => $v)
{
if ($k != 'pag')
{
$querystring .= "&".$k."=".$v;
}
}
//inizializzo una stringa vuota in cui appenderò l'output del menu'
$menu = '';
//serie di condizionali in cascata per costruire il menu'
if($numpages <= $num_links+1)
{
for ($pagina = 1; $pagina <= $num_links; $pagina++)
{
if (($pagina-1)*$x_pag == $pag)
$menu .= "<span class=\"pag_selected\">$pagina</span> ";
else
$menu .= "<a class=\"pag_link\" href=\"?pag=".($pagina-1)*$x_pag."$querystring\" title=\"Vai a pagina $pagina\">$pagina</a> ";
}
}
//se la pag corrente è tra le prime $num_links/2 --> stampo i primi $nun_links link
else if($pag/$x_pag <= floor($num_links/2))
{
for ($pagina=1; $pagina<=$num_links; $pagina++)
{
if (($pagina-1)*$x_pag == $pag)
$menu .= "<span class=\"pag_selected\">$pagina</span> ";
else
$menu .= "<a class=\"pag_link\" href=\"?pag=".($pagina-1)*$x_pag."$querystring\" title=\"Vai a pagina $pagina\">$pagina</a> ";
}
$menu .= "<a class=\"pag_link\" href=\"?pag=".$numpages*$x_pag."{$querystring}\" title=\"Vai all'ultima pagina\"> >> </a> ";
}
//se la pag corrente è tra le ultime $num_links/2 --> stampo gli ultimi $nun_links link
else if($pag/$x_pag > ($numpages-ceil($num_links/2)+1))
{
$menu .= "<a class=\"pag_link\" href=\"?pag=0{$querystring}\" title=\"Vai alla prima pagina\"> << </a> ";
for ($pagina=$numpages-$num_links+1; $pagina<=$numpages+1; $pagina++)
{
if (($pagina-1)*$x_pag == $pag)
$menu .= "<span class=\"pag_selected\">$pagina</span> ";
else
$menu .= "<a class=\"pag_link\" href=\"?pag=".($pagina-1)*$x_pag."$querystring\" title=\"Vai a pagina $pagina\">$pagina</a> ";
}
}
//Altrimenti la pagina corrente è una dell centrali --> stampo i $nun_links/2 link prima ed $nun_links/2 link dopo
else
{
$menu .= "<a class=\"pag_link\" href=\"?pag=0{$querystring}\" title=\"Vai alla prima pagina\"> << </a> ";
for ($pagina = ($pag/$x_pag)-floor($num_links/2)+1; $pagina <= $pag/$x_pag+ceil($num_links/2); $pagina++)
{
if (($pagina-1)*$x_pag == $pag)
$menu .= "<span class=\"pag_selected\">$pagina</span> ";
else
$menu .= "<a class=\"pag_link\" href=\"?pag=".($pagina-1)*$x_pag."$querystring\" title=\"Vai a pagina $pagina\">$pagina</a> ";
}
$menu .= "<a class=\"pag_link\" href=\"?pag=".$numpages*$x_pag."{$querystring}\" title=\"Vai all'ultima pagina\"> >> </a> ";
}
//restituisco il risultato della query, e l'output del menu'
return array(mysql_query($query),$menu);
}
(quota e fai copia incolla dal "sorgente")
fammi sapere... ovviamente la invochi come ho detto sopra..