Blog.php doesn’t work with /page/2/ in WP2.0

I’ve installed WordPress 2.0 and I’m trying to use it as a blog and CMS. It’s installed on
https://rommesol.c136.cphost.dk/ (main page) – and – https://rommesol.c136.cphost.dk/blog (blog and archive)
(btw. it’s not in english)

I’m using a static frontpage and have the blog located as the permalink /blog all as described in https://codex.www.ads-software.com/Pages . Further more I’ve done as described in https://www.ads-software.com/support/topic/35565?replies=3 to get the “Next Page” and “Previous page” links to work. But it doesn’t work in WordPress 2.0. Whenever one of the links are selected the result is the “404”-page

As far as I can tell it’s not a problem with the .htaccess file. No matter what how the request for page 2 is passed to index.php it won’t fetch the blog.php template.

Does anyone have any good suggestions to what might be wrong?