Try running the query as a UNION ALL instead and see if your query plan is any better. While it shouldn't make a difference when you upgrade to SQL 2008, SQL 2000 was not always so good parsing OR conditions.
DECLARE @LName --HTML encoded last name as input parameter from user
SELECT * FROM
(SELECT LNameComputedColumn
FROM SomeView xtra
WHERE @LName <> '' AND xtra.LNameComputedColumn=@LName
UNION ALL
SELECT LNameComputedColumn
FROM SomeView xtra
WHERE @Lname='')