I've discovered that it's all about the order in which you do things.
I had installed mod-perl2, which required apache2-mpm-worker (which uses threads).
I then tried to install mod-php5. mod-php5 can't use threads and so needed me to uninstall apache2-mpm-worker and install apache2-mpm-prefork. Which in turn needed to uninstall mod-perl5 as it depended on it.
However, mod-perl2 doesn't actually require 'worker'. It can use 'prefork' if it needs to. It just prefers worker.
So if anyone comes along and needs to get both installed:
- Install mod-php5 and let it install apache2-mpm-prefork
- Install mod-perl2 and it will be happy
If you do it around the other way, you'll thing (as I did) that you can't install both on the same system via the package manager.