Time Machine stopped working after upgrading to Yosemite
I had the same problem.  At the Apple troubleshooting site, it stated that the initial backup after an upgrade will take a long time.  I hit "Back Up Now" before bed, and when I got up in the morning, it had completed the Back Up.  After the initial Back Up, it works just fine now!