Corrupt Time Machine? Check your router!
I've been running Time Machine off a WD My Book World II NAS for years now. Everything worked swell until a few days after upgrading to Mountain Lion when I started getting errors that my Time Machine had gone corrupt and needed to start from scratch. The error would happen on both laptops but at different times. Every few days.
My first instinct was to blame the combination of Mountain Lion and the NAS. I scoured the web for solutions but none of them worked for me. I was resigned to spending $299 on a Time Capsule when I had a perfectly good router and a perfectly good NAS. Or so I thought.
One day the wireless radio in my router went kaput; it ceased to function but the router was still working. I started using a very old AirPort Express in bridge mode as a radio. Then I started getting network issues: packet loss, connections dropping, etc. I realized something funny was going on so I thought I'd try a new router. The AirPort Extreme has great reviews and all sorts of new fancy technology that my old router did not. Plus it's very pretty. So I picked one up from the Apple store over a week ago.
Lo and behold replacing that dying router solved my Time Machine issues! I should have seen the signs long ago but there were so many red herrings distracting me.