Hmmm. This was a known bug with pre-RTM builds of LINQ-to-SQL, but from what I read online this was a fixed problem for equality comparisons in RTM (although still broken for Contains() comparisons).
Regardless, here's a thread on MSDN forums with some workarounds detailed:
http://social.msdn.microsoft.com/Forums/en-US/linqtosql/thread/4276ecd2-31ff-4cd0-82ea-7a22ce25308b
The workaround I like most is this one:
//define a query
IQueryable<Employee> emps = from emp in dc2.Employees where emp.NationalIDNumber == "abc" select emp;
//get hold of the SQL command translation of the query...
System.Data.Common.DbCommand command = dc2.GetCommand(emps);
//change param type from "string" (nvarchar) to "ansistring" (varchar)
command.Parameters[0].DbType = DbType.AnsiString;
command.Connection = dc2.Connection;
//run
IEnumerable<Employee> emps2 = dc2.Translate<Employee>(command.ExecuteReader());
BTW, another case I saw this happening was in a table with odd distribution of values (e.g. 50% of table had the same value) meaning that, given the parameter is unknown to SQL Server at plan compilation time, a table scan was the best plan available. If your distribution is also unusual, then the workarounds above won't work, since the scan won't be coming from the missing conversion but rather from the parameterization itself. In that case, the only workaround I'd know would be to use an OPTIMIZE FOR hint and manually specify the SQL.