Is the HD full? Are you using a spinning as opposed to SSD drive? Time machine has given me issues with both..but were resolved. I've used TM for years but will concur with the above: (ALSO) use CCC or SuperDuper. I also use CCC which has excellent support and is seamless.
I've found Time machine buggy since day one. Maybe it's all the stuff I choose to protect from its grasp? It seems to work for a few months, then have trouble finding older copies of stuff. I've always used Super Duper. Now I know longer bother with Time machine, unless I'm doing a specific project that could benefit from hourly BU. When done with such, I turn Time Machine off. For me, it's always offered a false sense of security.
Like Partron22 and others elsewhere, I long lost trust and confidence in Time Machine as a system restore solution. I've seen Time Machine backups fail mid-operation all too often for me to believe that it is anything close to approaching reliability.
For major upgrades, I use Carbon Copy Cloner to generate a bootable external clone of my working system drive. I think of Time Machine as a potentially useful incremental backup service since the last clone.
The old system administrator's adage still applies: if it's worth backing up, it's worth backing up twice.
Some people (like your typical modern IT staffer) swear by three different backups with at least one backup in a secure offsite location. That's best practice but not always practical or convenient for Joe Consumer.