No, replacing your hard drive has nothing to do with it. There is a problem with your backup drive. As far as Time Machine is concerned replacing a drive is no different than buying a new computer. Time Machine will need to make a brand new backup from scratch.
If you have a large enough backup drive this may not be a problem. Otherwise, you may not have sufficient space to maintain a new backup and keep the old one. So, I would suggest under the circumstances that you erase your backup drive, then start a new Time Machine backup from scratch.
Drive Erase
1. Open Disk Utility in your Utilities folder.
2. After Disk Utility loads select the volume you wish to format from the left side list. Click on the Erase tab in the Disk Utility main window.
3. Set the format type to Mac OS Extended (Journaled.) Click on the Erase button and wait until the process has completed.
For additional help with Time Machine: Visit Pondini's Time Machine FAQ for help with all things Time Machine.