First I would do some checks on the disk itself. Start by running Repair disk from Disk Utility in your Utilities folder. Check the SMART status if you can too. If all seems to be ok then can you actually see what is on the disk in Finder?
Pondini is the expert on Time Machine and his diagnostics are a good place to start troubleshooting TM generally.
Thanks for the guidance. When I ran Disk Repair it took a while to run and, in the end, it said it found too many problems to repair the disk. It said all the data is still there, that I should back it up, reformat it, restore the back-up then hopefully I could start using Time Machine again. The problem I have with that is that I don't have anything to back the external hard disk up to. All that's on it are Time Machine back-ups. Since I can't access them now anyway, is there any problem with just going ahead and reformatting the disk (not doing the back-up) and then just starting to use it with Time Machine again once its reformatted? I know that, during the time until I do the first back-up with the newly reformatted disk, I will be exposed and without any back-up, but shouldn't the disk work fine again once it's reformatted? Or is there a chance it's too corrupt to work even after being reformatted? Other suggestions?
I would think the disk is failing and although it may move data to good segments and look ok for a while, eventually something critical will fail and you will lose everything. Maybe I am being pessimistic and you could try to check the SMART status and use more powerful tools than Disk Utility, such as Disk Warrior.
I would buy a replacement disk and start a new backup set, either using Time Machine or make a bootable clone using Carbon Copy Cloner (CCC) or SuperDuper etc. The clone has some advantages in that you can conduct more tests from outside your system, do erase/installs etc.