Running Catalyst under FCGI is a b*** on shared hosting!
Not really a Perl issue so much as a customized site issue--if you're trying to do much more than what the hosting provider gives you as part of the package, shared hosting can be a big pain. If you're using Catalyst you're probably pushing beyond what most shared hosts support effectively. Virtual servers have gotten fairly inexpensive and you can get one where you have complete control over the configuration (right down to which BSD or Linux distro) that makes it much easier to manage something where you're doing anything special. You can be pretty sure with a VPS that nobody but you is going to upgrade some module to a new version and break all your stuff. You can also set up the server (Apache, Nginx, or whatever) to deal with requests how you want so you don't get the overhead of starting a whole new process for every hit. It sounds like a little more work on the front end, but it's less work than trying to squeeze what you want into someone elses non-optimized, inflexible setup, when you can probably find plenty of reliable recipes on how to set up something that really does what you need.