Manually delete all entries from the core_url_rewrites folder (make sure to reindex afterwards)

yr_delete_urlrewrites.php

<?php
require_once 'app/Mage.php';
Mage::app();
Mage::app()->setCurrentStore(Mage_Core_Model_App::ADMIN_STORE_ID);
$urlRewrites = Mage::getModel('core/url_rewrite')->getCollection();
foreach($urlRewrites as $urlRewrite) {
    $urlRewrite->delete();
}