For the spelling portion, I've had great luck with Text::Aspell. It's simple and effective. There's also a driver for it for Search::Tools, if you're using that to build your engine.

For semantic similarity, that's a much different (and harder) problem, and I think the other posts have some good leads for you. But I think if you can roll out a Text::Aspell based solution quickly, your client may realize that's what they want anyway.