Thanks. But unfortunately, most of those google results are for troubleshooting installation of Catalyst itself.
The problem wasn't catalyst, but rather fastcgi. Turns out there's FastCGI issues with sites hosted here on Apache2 servers. Support helped me out with that though. Gotta love those guys.
There was another issue though. After tailing my error logs a bit I discovered that some of my modules weren't being seen.
For anybody who's reading this and having similar issues, I solved mine by adding the following to myapp_cgi.pl and myapp_fastcgi.pl/dispatch.fcgi:
where [user] is your shell login, obviously.
I don't know if that means the wiki isn't accurate, or if it means something's wrong with my environment. In any case, if you're having that problem, give the above a shot.
Sheesh, what a headache. But finally, I can start working on a perl website.