Update Query Taking 23 Seconds

I am not sure if I am in the correct location or if I should be in the SQL forum but here is my question:

I have an update statement that goes out through SQL 2000 through a local linked server to another SQL 2000 server on my machine. When I run the update in Query Analyzer it takes less than a second. When I run it in my C# code using the SqlCommand object and parameters it takes me ~23 seconds. If I remove one of the parameters it goes down to ~15 milliseconds. Has anyone heard of this happening?

The parameter that I remove is a simple char(10) column that isn't the primary key and is used in the WHERE statement. There isn't an index on the field.

23 Seconds
Update table Set column = @val WHERE field = @field AND other = @other
15 milliseconds
Update table Set column = @val WHERE field = 'values' AND other = @other