Can't believe it's almost 8 years since I wrote this Indonesian article about "8 things that make Perl relatively unreadable".
To summarize, I think the readability issue in Perl largely boils down to the high usage of symbols/non-alphanumeric characters (e.g. regex and special variables). This admittedly won't change for years to come, as Perl 6 also offers us lots of new operators, even allows us to define new ones, using the full range of the Unicode charset! So we will almost certainly be hearing and need to be fighting against this meme for a long long time.
I also believe that most of the complaints about Perl being unreadable come from non-Perl users. When they read some code, they expect it to be able to read/guess it based on the prior knowledge of some other programming language. For example, even before I started learning French or German, I could guess the general meaning of some French and German (or some other European language) phrases based solely on my knowledge of English. This does not happen with, say, Chinese or Math or regular expression, as the symbols are just gibberish to the non-initiated.
Perhaps marketing that Perl is one of the hardest languages to master will attract more people to learning it, as that's what's happening with Cantonese and some westerners.