I just upgraded to ML and my Time Machine says "Waiting to Backup".
Is the cause of this got to do anything with Spotlight indexing?
It's possible. You should be able to click the Time Machine icon, then Open Time Machine Preferences... and then it will tell you a more detailed reason such as the following:
It seems that the Index was slowing down TM as well, but TM was just being slow overall and works fine.
I had the exact same thing here. In the Time Machine preferences, you have the list of your drives plus an icon labeled Add or Remove Backup Disk. In this list, right click on the icon of the disk and select Back Up to "..." Now. That worked for me.