Si pones el código que usas .. tal vez veamos el error mejor .. De todas formas .. ya que usas Mysql podrías hechar un vistazo a este paginador (código) "Paginator de Jpinedo". Si te fijas .. no usa para nada "mysql_data_seek()" pues usa LIMIT para ir entregando los grupos de registros que necesitas por página y no como (tal vez lo estás haciendo o intuyo que haces) .. obtener toda la consulta SQL y moverte por el resultado pero siempre haciendo una consulta total a los posibles N resultados ..
http://jpinedo.webcindario.com/
Un saludo,