This behavior is most likely due to the renderer.
The renderer that MATLAB is using to display the images is very likely a bitmap renderer such as OpenGL or zbuffer (the figures you sent me used the ‘zbuffer’ renderer). EPS formats are essentially vector formats so it is best if the renderer that you use to generate the figure is also a vector renderer ('painters').
As you are likely using a bitmap renderer, MATLAB has to first convert the bitmap into a vector, and this conversion of bitmaps to vector images is often a time-consuming and inefficient process.
This is why your images appear incorrect when you print them.
1) Change the renderer of the figure before you draw your figure or before you export. You can use the following command:
2) Change the renderer used by the PRINT command. By default it uses the same renderer that the figure uses, so you would have to type the following command to over-ride this:
>> print -depsc -tiff -r300 -painters <filename>.eps
>> print -depsc2 -tiff -r300 -painters <filename>.eps
Also, I suggest you use a PostScript printer or viewer to view your EPS files. This is just to make sure that you are viewing your actual EPS file and not the TIFF preview.