I know this is old and I'm nerco-ing it, but since I got here by a search, I figure this may help someone else.
I had the same issue when I first configured TimeMachineTime Machine to use my NAS - every few weeks, I'd get the popup at the top of this thread. It was very frustrating. I noticed over time, however, that this only happened on particular days of the week. And I then realized that it only happened during the weekly scrub (Monday morning) or resync (Tuesday morning) operations. So I obtained a copy of "Time Machine Editor" which lets you tell TimeMachineTime Machine when it can and can't run, excluded Monday and Tuesday mornings, and voila, problem solved.