This error is caused by graduated or radial fills, complex or compound paths, text effects, masks.

Solutions

Try simplifying the document.

If you used the magic wand in PhotoShop to mask some images: recreate the masks using the drawing tools of PhotoShop. This simplifies these often very complex curves.

Drawing programs like FreeHand offer filters to automatically simplify curves.