Código PHP:
Ver original$query2= mysql_query("SELECT nombre FROM usuarios LIMIT " . --$pagina * $items_por_pagina . ", " . $items_por_pagina);
La consulta es esa, asi que la tienes bien. El error estará en otro sitio.
¿Estas segura de que $pagina nunca es menor que 1, ni que nunca superará el número de páginas?
En la consulta no has usado el buscador, que suele ser un LIKE '%$search%' sobre algún campo, en las dos consultas, la del count y la de paginación.