Yes, I agree, LyX can handle eps, but you need the imagemagick package. However, I think the problem here is that the size cannot be determined. I had that kind of problem before in Latex, and I solved it by setting the width in Latex, which I believe is equivalent to setting width in lyx.
Check in Document Settings that the graphics driver is set to "default" and not to "dvips".
JMarc