I think this is a problem with Evince. I just tried this (linking to both a PDF and an ODS file). LyX exported my document correctly (using pdflatex). Opened in Acrobat Reader, both links work correctly. Opened in Evince, both links produce the error message you got.
Paul