Does this happen all the time - No, only on certain documents. The documents in question were received from another company by email. On closer inspection the actual .pdf files appear to be corrupt. I now believe the problem lies with the .pdf files, not acrobat. The error message is just a bit ambiguous to say the least.
Did you try re-installing Acrobat - No, the same error occurred on several different machines, so probably not an installation issue.