Why are regular expressions so controversial?

I don't think people object to regular expressions because they're slow, but rather because they're hard to read and write, as well as tricky to get right. While there are some situations where regular expressions provide an effective, compact solution to the problem, they are sometimes shoehorned into situations where it's better to use an easy-to-read, maintainable section of code instead.

I don't think they're that controversial.

I also think you've sort of answered your own question, because you point out how silly it would be to use them everywhere (Not everything is a regular language 2) or to avoid using them at all. You, the programmer, have to make an intelligent decision about when regular expressions will help the code or hurt it. When faced with such a decision, two important things to keep in mind are maintainability (which implies readability) and extensibility.

For those that are particularly averse to them, my guess is that they've never learned to use them properly. I think most people who spend just a few hours with a decent tutorial will figure them out and become fluent very quickly. Here's my suggestion for where to get started:

http://docs.python.org/howto/regex

Although that page talks about regular expressions in the context of Python, I've found the information is very applicable elsewhere. There are a few things that are Python-specific, but I believe they are clearly noted, and easy to remember.