How did you narrow down to the point that character set could be the problem
we have 2 database one database is with character set WE8ISO8859P1 with this database you have sql query that run fast with a good execution plan
on the other database character set is WE8MSWIN1252 the same query run slower with very bad plan. It is possible that the character set have influence on the optimizer