This problem has been reported several times. I have a synology network drive that I use Time Machine with and I get this error message at least once a month. Only solution is to completely delete the existing Time Machine file and start a new backup...meaning Time Machine is not reliable. I have contacted Applecare about this and they say that my network drive is not supported by Apple (because its not a Time Capsule) therefore will not help me trouble shoot the problem. I contacted Synology, who is the manufacturer of my network drive, and they say it's apples problem. Basically no accountability by either company. Good luck!
Are you running the latest firmware on the synology? It is important as TM changed a bit with Lion and you need to keep firmware up to date to match the changes.. but Apple are a closed company now and they do tend to only make stuff within their own family work together.. there are other solutions than TM that may well work better with non-apple NAS.
To yonny, if you are using TC are you using wireless? There is no doubt that wireless has a lot more issues and if you have issues try using ethernet instead and see if the problem keeps happening.
Pondini has several suggestions.. but there is no single fix.
Read through the troubleshooting area.. as a lot of things can happen.
If you did a Lion update over SL it seems to be less stable than a clean install.. If it bothers you, I would seriously look at clean install.
I have a Synology 1511+ and had the same issue. Except my backups would only corrupt every month or two.
After lots of searching I found the issue is backing up over wifi to the NAS. I found the solution to this was to install a small app: Time Machine Scheduler (free).
It can be found here: http://www.klieme.com/TimeMachineScheduler.html
All you need to do is install, and set backups only to run over Ethernet. Works great for me as I use my mac 50/50 between my workstation and wirelessly around the house. Haven't had an issue since.