If your software really gets better over time, and if you've accepted the idea that backwards compatibility is technical debt, the important question is "How do I pay down that debt?"
The only approach I've seen work is to establish and maintain a sane deprecation policy. Specific details depend on your project and your users (and, likely, your availability to perform the work -- community-driven projects performed mostly by volunteers have different characteristics from paid projects), but the principles are the same.
Start with a regular release cycle. I prefer monthly releases for free software projects, but several projects do well with quarterly or twice-a-year releases. There are tremendous other benefits, but if you can make and meet your committment to releasing new versions of your software on a regular cycle, you add predictability to the process. Not everyone will upgrade with every new release, especially if you have a short cycle period, but you demonstrate frequent progress -- and you have to keep your software stable to have a hope of maintaining this release schedule.
Mark deprecated features as deprecated and give a timeline for their removal. In general, that's one release cycle. It can be more, but it can't be fewer. The severity of deprecation depends on the scope of the change. Perhaps adding a warning to a deprecated feature will help people know to upgrade. Perhaps you can provide a backwards-compatibility feature as an optional extension. You must notify people that there will be change, so that they can prepare for it.
Note that aggressive release schedules, such as monthly releases, may be too short a period for larger deprecations. Appropriate periods depend highly on the nature of your work, but public projects probably should have a three month warning period for significant deprecations.
Remove the deprecated feature when its time has come. Get rid of the code. Stop carrying that baggage around.
That sounds easy, doesn't it? It is! All it takes is discipline, committment, and -- okay, you have to document your deprecation policy and refer to it prominently. Some people will complain that they want to upgrade to new versions of your software which behave the same way as old versions without changes. Ignore them. Desire doesn't make paradoxes logically consistent, even if you really really want it.
Before you post a comment, please note what I didn't say.
I didn't say "Break old features for the sake of breaking them."
I didn't say "Deprecate features that people are using for the sake of expermenting with new ideas."
I didn't say "Never undeprecate a feature" or "Never extend the deprecation or warning period if the change is difficult or widespread."
You still have to use your best judgment -- but once you've achieved the discipline of regular releases and have written your support policy, you have the benefit of being able to discard old code and shave off the rough spots of misfeatures until they're right. It's not always easy to reach that point, but it's always valuable to do so.
For Perl deprecation should be much harder - Perl is usually bundled with OS and many packages in OS repositories depend on having exact version. If you upgrade perl, you will need to install any package depending on it manually.
So installing any fresh CPAN module manually is easy and in many case will result in no problems as they usually have low number of packages depending on them. Upgrading Perl is hard as too many packages depend on it. It's problem of big popularity :).
One of the solutions is to deprecate features gradually, by removing them by required version ("use 5.xx.xx") first. Another solution is to provide a back compatibility layer. I tried to do this with 3-arg open and several other features, but then decided that versions less than 5.6 are too rare for this to be useful enough. But it is possible. Third solution is OS upgrade without OS reinstalling.
Sounds great! When is Perl5 going to implement something like this? :-)