The current pagination class expects a pagination_url in the form "http://example.com/this/that/other", to which the page number will be attached.
It does not support random segment numbers (how should it detect the correct one), it also does not support segments that contain other data then just the page number.
There is a new pagination class planned for 1.3 that will solve these issues, but it isn't finished yet.