@michaelh – for information: the wp_link_pages() construct won’t work out of the box on WP >=2.7 if the front page is static and also contains either more or nextpage links. Works fine on other static pages, and also on posts.
See https://www.ads-software.com/support/topic/313281?replies=1 for a crude workaround for nextpage [doesn’t support “more” yet].
The theme issue is more complex because there are so many of them which are not always entirely good coding quality or which do unusual things with the loop. I’m currently trying to rewrite the code I posted at that link as a plugin with filters so that it is generically more useful and will work regardless of theme.
