Distribution/Version: Ubuntu Hoary

1. Create an ecapsulated PostScript file (I used OpenOffice2 Draw, save as EPS). 
2. double-click on it in Nautilus. You get this error message:

 The filename "test.eps" indicates that this file is of type "Encapsulated
PostScript image". The contents of the file indicate that the file is of type
"PostScript document". If you open this file, the file might present a security
risk to your system.

Opening the file in emacs, I see that it starts with the lines

%!PS-Adobe-3.0 EPSF-3.0 
%%BoundingBox: 0 0 273 317

which, AFAIK, is exactly the correct header for EPS files.