1) use the TwentyTen theme
2) create a template using the 'Page of Posts' example from http://codex.wordpress.org/Pages#Creating_Your_Own_Page_Templates.
3) create some post with a category - more than a page worth
4) create a page called 'MyTest' and assign it the 'PageofPosts' template
5) add a custome field 'category' and the name of your category
6) test it out, it will go to the second page with no problem. If you look at the link you will see: http://yourdomain.com/?page_id=50&paged=2 (the 50 is my page id)
7) go to dashboard->settings->reading and change 'Front Page Displays' to 'a static page' and set the Front Page to MyTest
8) go view the page and try to go to the next page.
What happens is that the first page is fine, but when you try to go to the next page, the link is http://yourdomain.com/?paged=2 and the index.php is executed, not the page you specified.
Is this a bug or can't you specify a page that has a template as the front page?