A mi me ocurrió lo mismo, no se mostraba la barra de paginación, la solución es añadir la función del plugin para mostrarla:
El código de raydenslayer es correcto, veo que tienes definido el div "pagination" pero no habrá cogido la función, déjalo de esta forma:
<div id="pagenavi">
<div class="fixed"><?php wp_pagenavi(); ?></div>
</div>
Y aquí te dejo la url oficial del plugin con la instalación por si tienes algún problema:
http://wordpress.org/extend/plugins/.../installation/
Salu2.