I had the same problem, no idea where it came from. I had a jailbroken iPhone 3G and switched to a non-jailbroken iPhone 4, i.e. I transferred the backup to the new phone, which worked. Some time later, however, I got that error message. I tried the solution above, I even deleted all backups, even the ones not related to that phone, but the error persisted.
I found a solution in a comment to the thread iPhone could not backup because backup file was corrupt or not compatible, fix, more details in a following comment. Here’s what to do, summarized:
(This is a solution for Windows (7), which doesn’t apply to the OP, but his problem seems to have been solved already at any rate.)
- Close iTunes
- Make sure your Explorer displays hidden files
- Go to
C:\Users\username\AppData\Roaming\Apple Computers\MobileSync\backup
- Delete everything there (or move it somewhere else, to be on the safe side)
And done. In my case, I deleted two folders with long, cryptic, alphanumeric names, one empty, the other over 1GB in size. When I opened iTunes again, I could create a brand new backup without any errors.