The old/new major version sounds entirely sane to me. Version 1.x is available and is the approved version for old versions of Perl. It will get minimal love going forward. Version 2.x is the shiny new version tested against current versions of Perl back to say 5.10 (because that's when a lot of interesting stuff changed and there are probably still OSs around in maintenance mode with 5.10 as their system Perl).
It is a well understood and common practise that a major version bump may break stuff. It sounds like the changes you propose hardly warrant a mojor version bump because, apart from the exports change, they are pretty much internal. However the major version bump sends a pretty clear message that changes are afoot so watch out.
Perl is the programming world's equivalent of English