I thought of reporting the bug, but Codex suggests asking some specialists before doing so :)
Here is a workflow that lead to a possible bug.
I created a page using a custom template and saved it (the slugname of this page was news and the permalink structure was - http://sitename/%postname%). In this template I use a new WP_Query object to get the posts from a custom post-type and I wanted to have pagination for these posts as well.
The loop went on nicely, I got my posts and the pagination worked well for the rest of them. Everything was good, but when I changed the slugname of this page from news to say ournews - paginations breaks... I get a 404 on the second page onwards. When changing it back to news - it works :) It looks like wordpress somehow memorizes the 'original' slugname and is unwilling to paginate when this slugname is changed.
Summary of the bug: pagination of custom post-type posts breaks after changing the slugname of the page they are shown on.