Yes it is common, and has been for many years. Shared hosting companies' customers are not by and large Perl developers. So they don't worry much about providing Perl support.

Get a Linode ... they have inexpensive, highly reliable virtual servers, great documentation; you will love it when you are in charge of your own Perl installation!