Yeah, that confirms the problem.
Sometimes the indexing process can get stuck. It's not unusual for the indexing process to fail if it's tried to be run from admin when you have time limits on the amount of time web processes can run. It is desired to have these time limits so that run away processes don't create bad experiences for customers but it is a pain when it comes to getting the indexes to run.
Do you have SSH access to the machine? If so, you can run a full reindex by going to the root of magento and running:
php shell/indexer.php --reindexall
Another note, indexers can have one of two different modes. One is "Update on Save". The other is "Manual". Generally, I recommend setting all indexers to manual and then adding a cron task to run the indexing process on a regular basis. Every 4-6 hours is normally sufficient on community edition.
... View more