What version of grep are you using? Not too long ago the grep in debian/unstable was awful with UTF strings. pg135.txt is project gutenberg's les mis. What were your times?

I no longer notice this behavior:

    dfc@motherjones:~$ grep --version 
    grep (GNU grep) 2.9

    dfc@motherjones:~$ time LANG=C grep asdf < pg135.txt > /dev/null 

    real	0m0.017s
    user	0m0.008s
    sys	0m0.004s
    dfc@motherjones:~$ time LANG=UTF8 grep asdf < pg135.txt > /dev/null 

    real	0m0.017s
    user	0m0.012s
    sys	0m0.004s
    dfc@motherjones:~$ time LANG=en_us.UTF8 grep asdf < pg135.txt > /dev/null 

    real	0m0.012s
    user	0m0.004s
    sys	0m0.004s

There is not a lot of info about this in debian bug 604408

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=604408

If memory serves me correctly this upstream fixed this sometime after 2.7.1 or 2.7.3

Funner fact: GNU grep used to be slow with UTF.