Most of the anti-Perl comments I've heard have been from people who really didn't know it very well, if at all.
Some of them might have glanced at some Perl code and saw a dense regex and dismissed it as "line noise". Well, yeah, if you don't know regexes you would be forgiven for thinking it was line noise, but if you did know regexes it should look no more like line noise than a similarly dense regex in any other language.
For a long time now, Perl has allowed regexes to be commented. Commenting dense regexes and splitting them up in to short regexes assigned to judiciously named variables is just good style in any language, and has been the norm in Perl for a long time. Furthermore, modern Perl style guidelines advise code to be written with verbose, English words instead of ancient Perl one-character special variable names.
So setting aside both dense, uncommented regexes and ancient single-letter special variable names, both of which have been recognized as poor style in Perl for decades now, I'm really not sure what the complaints about Perl readability are about. To me it looks really no uglier than any other mainstream language, and one could easily make the argument that any other mainstream language you care to name is uglier in some of its own ways.
If you include non-mainstream languages, some languages which have a lot of fans here on HN are arguably a lot less readable than Perl to someone only familiar with traditional Algol-style languages. In particular, I'm thinking of Forth and Haskell. Yet you rarely hear complaints on here about their readability.