Yep, similar issue.
First, after going into Time Machine Preferences after the ML install, there wasn't any indication of when the last and next backups were/are, or any usage info. I repointed Time Machine to my Time Capsule, which initially seemed to work. But when going into Time Machine recovery I couldn't see any of my previous backups.
So I decided to start over - create a new, encrypted backup (previous one from Lion was unencrypted). Turns out this requires deleted the old backup (which susprised me since I though multiple machines could back up to the same Time Capsule, and I assumed this meant there wouldn't be an issue with the same machine having multiple backups.) Deleted the old backup failed though. I couldn't delete the backup file directly through Finder either - it just sat there forever, no error, but no completion to the task. I couldn't reboot the iMac because of this - no reboots allowed during a Finder action, turns out. Rebooting the Time Capsule fixed this, at which point I just shut down the iMac and went to bed.
Next up this afternoon when I get home from work - try to delete the old backup file manually and establish a new encrypted backup.
My theory - something about the ML upgrade doesn't close down the Time Machine backup file. Turning Time Machine off then back on seems to reinitialize things properly - just repointing TM to the Time Capsule disk doesn't do the trick. (Unfortunately for me, I didn't try the off/on thing until after I had tried establishing a new backup. Cross my fingers my HDD doesn't crash or get corrupted between now and when I can establish a new full backup.
)