Yo reemplazaría:
if (!$pagina) {
$inicio = 0;
$pagina=1;
}
else {
$inicio = ($pagina - 1) * $TAMANO_PAGINA;
}
por:
if (empty($pagina)) {
$inicio = 0;
}
else
$inicio = ($pagina * $limite)+1;
¿Porqué?, simple, porque si $pagina es igual a 1, $inicio tomará el valor 0, por lo que habrá una página que mostrará dos veces el mismo contenido ya que comenzará en la misma parte.
Así nos evitamos darle un valor 1 a $pagina cuando esta esté vacía o sea 0, ya que se quita automáticamente la posibilidad de que la página sea 1.
La función empty retorna un valor 0 si es que no existe, asi que si el get lanza vacío, si o si, resultará, comprobado.
Ahora, un rooteo rápido, por ejemplo, si $limite es 10 elementos y el total es 25, significa que para la página 0, se presentarán los 10 primeros, para la página numerada como 1 serán desde el 11 -> (10*1)+1 hasta el 20 y asi...
Ahora, para el usuario que pedía hacer una paginación limitada, estuve desarrollando recién el código, te lo muestro y me dices si resulta, cualquier bug me mandas un correo a camilongo@live.cl, en este caso se muestran 3 links por página, ahi adaptala para 5:
//Incluímos el archivo de conexión
$limite= 10;
$pagina = $_GET["pagina"];
if (empty($pagina)) {
$inicio = 0;
$primera = true;
}
else
$inicio = ($pagina * $limite)+1;
//Obtenemos la información necesaria para paginar
$sql = "SELECT * FROM messages $condiciones";
$result = mysql_query($sql);
$tot_registros = mysql_num_rows($result);
$tot_paginas = ceil($tot_registros / $limite);
//Imprimimos los campos que requerimos
$sql = "SELECT * FROM messages $condiciones LIMIT $inicio,$limite ";
$result = mysql_query($sql);
while ($row = mysql_fetch_array($result)){
//Aquí haces lo que quieras con el arreglo row
}
//Mostramos las páginas limitadas
$pag_ant = $pagina - 1;
$pag_sig = $pagina + 1;
$p = $pag_ant - 1;
//Esto solo se hará si hay mas de una página
if ($tot_paginas > 1){
//Si es la primera página
if($primera==true){
echo "<b>0</b>" . " ";
for($i = 1; $i <= 2; $i++)
if($i<=($tot_paginas-1))
echo "<a href='index.php?pagina=$i'>$i</a> ";
}
else{
//Ir a la primera página
echo "<a href='index.php?pagina=0'><<</a> ";
//Imprime desde la pagina anterior a la actual, hasta la siguiente.
for ($i=$pag_ant;$i<=$pag_sig;$i++){
//En el caso que estemos en la última página, se imprimen los links a las 3 ultimas páginas
if($pagina == ($tot_paginas-1)){
echo "<a href='index.php?pagina=$p'>$p</a>";
echo "<a href='index.php?pagina=$pag_ant'>$pag_ant</a> ";
echo "<b>$pagina</b> ";
break;
}
else if ($pagina == $i)
echo "<b>$pagina</b>" . " ";
else
if($i<=($tot_paginas-1))
echo "<a href='index.php?&pagina=$i'>$i</a> ";
}
}
if($pagina<($tot_paginas-1))
//Si no estamos en la última página
//Ir a la última página
echo "<a href='index.php?pagina=".($tot_paginas-1)."'>>></a> ";
}
mysql_free_result($result);
Ojalá te sirva ;) Saludos
Usuarios: 
