Detecting Errors in .po files

My guess would also be that this is an encoding issue. Since the error already appears in the first few characters of the file the culprit is probably a byte order mark, which in utf-8 is encoded as the byte sequence 0xEF, 0xBB, 0xBF. The best way to check this would be to look at the file with a hex editor, or use an editor that can tell you whether the file contains a byte order mark.

For example in vim you can use set bomb? and it will tell you either bomb or nobomb.

Edit: Here is a blog entry of someone having the exact same error message caused by an utf-8 encoded file starting with a byte order mark.

It sounds almost definitely like an issue with BOM, PO files should not contain them. An alternative would be to run pocompile from the Translate Toolkit, since you are already using Pootle pocompile should already be installed on your system.