Made a local copy of live-site: all paths generate error 404

Question

Drupal version: 6

I've made a local copy of a site that is live, has loads of content and is configured to run in the Kurdish language.

Steps I did to accomplish this:
- Made a tarball of the Drupal installation and extracted it on my localhost
- Dumped the live-database and imported it locally
- Modified settings.php to reflect local database settings

When browsing to the local installation, the front-page seems to work fine (except for a few pictures not showing up, as well as the facebook like box generating a 404 error). Except: when clicking on any url, of any node-type, a 404 error is generated.

I tried to fix it with this proposed solution: http://www.paulmarc.org/learn/drupal/rebuilding-site-urls, but to no avail. It seems to me I have to rebuild the site, however: even invoking that path does not work and generates a 404 and is thus inaccessible.