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>