The biggest problem I've noticed for regex is we use it every once in a while and once it works we move onto other things. And a few weeks/months later, we have forgotten much of it and have to relearn it all over again. Whereas, you generally use your programming language ( C++, C#, Java, etc ) everyday to keep your skills sharp, regex is generally "set it and forget it" situation for most people. And as you noted, different languages/shells/etc implement their own flavor of regex which can trip you up.
It's similar to SQL when you think about it. You set up a query to get the data you need and move on to other things. And every RDBMs implements their own flavor of SQL which can complicate things.
I don't think regex is that specifically hard to learn, but you're fighting the escaping in your favorite language at the same time, so your learning is confounded.
Please do not forget the fact that after a couple of months, you want to make a small change, but you forgot the edge cases when you first created the regex :D
It's similar to SQL when you think about it. You set up a query to get the data you need and move on to other things. And every RDBMs implements their own flavor of SQL which can complicate things.