This may be a quite popular error when you try to re-index in Index Management page of Magento, especially after you upgrade Magento version. I faced this issue for a project recently and spent lots of time searching in Google. There are some ways to fix the issue but not all of them works. The best way for fixing this problem, in my opinion, is to repair the database using database repair tool developed by Magento core.
Here are few simple steps for you to repair the database:
1. Download repair tool from Magento and unzip the package.
2. Upload magento-db-repair-tool-1.0.php to your server
3. Backup your current database (call it 'database1'). Export this database and then import it into a new database (let's call it 'database2').
4. Install a fresh Magento using 'database2'.
5. Now open the the URL in browser: http://www.youdomain.com/magento-db-repair-tool-1.0.php (this URL can be changed if you do not upload the php file to root folder).
6. Enter 'database1' as 'corrupted' and 'database2' as 'reference'. Enter all necessary information and click 'Continue' button. Wait and see result.
No open the FTP and delete all entries under var/locks. Go to backend System > Index Management and try to re-index again. Hope this helps!