This was causing me grief for quite some time until I stumbled upon this solution. The pagination class must be surrounded by a parent div with text-align:center applied to it.

For Bootstrap 3

<div class="text-center">
  <div class="pagination">
    ...your code here...
  </div>
</div>

For Bootstrap 2.3.2 and prior

<div class=" pagination text-center">
  ...your code here...
</div>