I'm more amazed that it took 35 seconds in NoteTab light than I am that it only took 2 seconds in perl. 35,000 lines really isn't that much that it should take so long. That's only 1000 lines per second, which I would say is pretty abysmal.
Update: just out of curiosity, I tried doing a single-word replacement on a 35,000 line file (where every line has the word being replaced) in vim. Like your case, I don't know any way to get vim to time it for me, but based on wallclock seconds it took 7-8 seconds. On an UltraSparc running at a whopping 350mhz with an enourmous 256mb of ram. On the same machine, it took perl 1.137s.
This reiterates how horribly slow NoteTab is doing something that seems relatively simple to do. :-)
Update: I agree strongly with ww's sentiment about not starting an editor war. That certainly wasn't my intention, and hopefully it wasn't seen that way.