Problems with links after moving to a new server

I was asked to move a fully functioning wordpress-based site to a new server.

I’ve moved the files and the database, set everything up, and it all seemed to work. When I load the homepage of the site on the new location, the page loads as it should. Opening one of the internal pages, however, generates a broken link error.
The same goes for wp-admin: I get to the login screen, from there on I get broken link errors no matter what I try.

I can get the site to work by switching off Pretty Permalinks.
Using default “Ugly Permalinks”, everything works fine.

.htaccess currently contains the following lines:
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ – [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
Which, if I’m not mistaken, is the default wordpress .htaccess rules for Pretty Permalinks.

The server runs a plain vanilla Debian install. The site has been installed in a subfolder of /var/www

According to the sys-admin, mod_rewrite is enabled.
Since the site runs with Uggly Permalinks, I think we can rule out any problems with PHP or the database.