Clear all files inside of var/locks/ directory
Apply 777 permission to var/locks/
Recreate index executing shell commands:
php magentodirectory/shell/indexer.php -reindex catalog_url
For this you need to empty the table call core_url_rewrites from you database and again do this process. But first please take backup of this table and then empty it.