Time Machine new backup must be created

I have the latest firmware on my 3TB My Book Live. I am getting the infamous error “Time machine must create a new backup…”. Isn’t it supposed to be solved at the latest firmware ? I have got a retina display macbookpro.


Check if the link below helps, it seem to be an issue if you are trying to do the backup using a wireless connection. 



Check the link below


This might help

Thanks a lot for the answers however i have already gone through most of the suggested solutions. They are either just temporary solutions (database becomes corrupted after a while) or irrelevant with my case.

As my macbook pro does not have a wired connection (I have ordered an thunderbolt to ethernet adaptor just to see if anything changes when the first backup is done over a wired connection) and it is not acceptable to say TM does not work over wireless connection, i am still waiting for an update either from WD or Apple.

Well i guess have to wait with fingers crossed.:confounded: