Most common error is that the URI segments are counted wrong. If your page URI is /admin/pages/index, and you want the second page to be /admin/pages/index/2, the URI segment number is 4.
If you don't pas a pagination_url, it will be set to Uri::main(), which is the URI that is used to get the page containing the pagination.
So you need to count the number of segments on that (excluding hostname, including controller, method and parameters). The uri_segment for pagination is that count + 1.
If you say that with 3 it works, but pagination gives errors: what errors? What link is exactly generated when you look at 2 or -> ?
You're going wrong in your code somewhere, but I can't figure out where. Pagination is used heavily on a daily basis, and most of our apps run on 1.8/dev, so I'm pretty sure pagination isn't broken.
Which means that if you specify 4 as uri_segment, you get the exception "Not enough segments in the URI, impossible to insert the page number", because segment 4 containing the page number can not be added because there is no segment 3.