Resetting Spotlight can be done as follows. I don't know how recommended this is, but I don't think it's really dangerous and I've done it twice (last week after installing Lion, and a few years ago when all older backups had somehow become grayed out).
If someone else knows a solution that does not involve deleting the older backups, please feel free to provide it though.
(1) Go to "System Preferences" and then "Time Machine Preferences". Turn Time Machine off.
(2) Mount your Time Machine backup disk (I assume people know how to do this, e.g. by browsing to it over the network and double clicking the Sparsebundle file).
(3) Open Finder, in the Finder menu to to "Finder", "Preferences" and then to the tab "Sidebar". Make sure that under "Shares" "Connected Servers" are enabled, and under "Devices" "Hard Disks".
(4) Go to "System Preferences" and then "Spotlight". Go to the privacy tab. Click the "+", add your boot disk, and your Time Machine disk. They should be visible in the sidebar due to step 3

.
(5) Now open a terminal, browse to /Volumes/<Your boot disk>. If you run "ls -la" you should see a file called ".Spotlight-V100". Remove it by running "sudo rm -rf .Spotlight-V100". Then browse to /Volumes/Time Machine Backup, and also remove ".Spotlight-V100".
(6) Go back to the privacy tab in "System Preferences" and "Spotlight". Remove your boot disk and your Time Machine disk from the list of directories that are not indexed by Spotlight.
(7) Wait until reindexing has finished. This may take several hours to finish.
(8) Re-enable Time Machine.
I don't know about the problem with insufficient disk space, if you run "df -H" in a terminal you can see the system's opinion on how much space is left.