So now, for a solution - I converted the eps to pdf manually using convert, that cuts off a good 1 in on the right side of the figure.. so
convert is not a good choice for eps files.
I converted it to jpg instead and everything seems to be fine.. I'm not sure why there's a problem with the eps figure - I generated it using Adobe Illustrator.. (and maybe that's it ;-)) ... is there a way I can specify that while running pdflatex, I want the eps images to be converted to jpg instead of pdf? Then I can define a converter for eps to jpg in lyx and all should be well I hope...
eps to jpg makes only sense for _real_ pictures, but not for drawings.
you can try to install VTeX/Free, which is very easy
http://www.micropress-inc.com/linux/
instead of latex you choose as converter for dvi vlatex. It understand ps,eps,gif,pdf,jpg and any PsotScript stuff from pstricks and generates by default a PDF file.
Herbert