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>