The most common problem with including graphics is an incorrect bounding box (see section The bounding box comment). Complain to whoever wrote the software that generated the file if the bounding box is indeed incorrect.
Another possible problem is that the figure you are trying to include does not nest properly; there are certain rules PostScript applications must follow when generating files to be included. The Dvips program includes work-arounds for such errors in Adobe Illustrator and other programs, but there are certainly applications that haven't been tested.
One possible thing to try is the `-K' flag which strips the comments from an included figure. This might be necessary if the PostScript spooling software does not read the structured comments correctly. Use of this flag will break graphics from some applications, though, since some applications read the PostScript file from the input stream, looking for a particular comment.
Any application which generates graphics output containing raw binary (not ASCII hex) will probably fail with Dvips.