Sorry for the trouble this is causing! The first thing to do is make sure that you're running fully up-to-date copies of OmniFocus on all your devices. (Sometimes there's more than one copy of the app installed on a Mac, so you'll probably want to use Spotlight to locate any older copies that may still be on the machine. If you find any, move them to the trash.)
The current release of the Mac app is version 1.7.5, which you can grab
from this link.
Next, check the very bottom of the Settings screen in OmniFocus for iPhone to make sure that you have version 1.5.3 installed. (Tap the toolbar button that looks like the letter "i" in a circle to bring it up.) If you have an earlier build of the app installed, the "Update" screen of the App Store app on your phone will help you grab the most recent release.
Previous versions of OmniFocus could start showing this error message if sync was turned off and then back on while the various devices weren't fully synced up. You'd end up with some transactions attached to the database in a way that didn't make sense, thus causing this message to appear. That's one possibility here. If there's an older version of OmniFocus in use, it could be attaching some transactions in a way that doesn't make sense; that would cause the other devices to start showing this message.
Another possibility here is if the "compact database" button or menu item was used on one device while the other one had un-synced changes. When that happenes the message is not an error. When the other copy of OmniFocus compacted the database, it meant that this copy was left with some transactions that it can't attach. If this sounds like what you're seeing, the solution would be to let OmniFocus compact the database on it's own schedule rather than manually trigger it.
Those are the two main possibilities I can think of off the top of my head, but there may be others that I'm not thinking of. The best thing to do if neither of these sound right would be to
contact the support ninjas so they can examine your sync database, figure out what's going on, and help get this sorted out. Sorry again for the trouble this is causing!