I would say APC on Shared Hosting plans is generally not a good idea.
The answer of your hosting is right but that's not the only reason.
When you get a Shared hosting you should be aware that you're not the only one who's using the server where your site is hosted. Depending on the hosting company's server, there may be 300 (or more) clients who're also hosting their sites on that machine.
Often those sites have MANY php files. For example a joomla 1.6 driven site has ~3000 php (~10mb) files (includes the site and admin panel).
Imagine all of those 300 clients are using the Joomla platform and the sites are
- Visited very often
- Generate average server load
That means all of those clients will have ~900000 files to be eventually cached - ~3000mb RAM will be used only for caching the php files. As you know in APC you can also store "User cache entries" where you can usually store settings or serialized objects. I can't say how much RAM will go there because it depends on what you store, but let's say another extra 50-100mb.
For now we've used about 3,1GB RAM.
Now add some RAM needed by the basic services to run - Apache, FTP, PHP, MySQL, PostgreSQL, SendMail and server backup tools. You'll probably end up somewhere near 5-6GB RAM that will be almost permanently in use.
The other problems with APC come when you cache - everybody can see what you've cached (as far as I know). So you'll probably need to encrypt what you store - this will require more CPU because you'll be encrypting/decrypting all the time. Also if somebody accidentally clears the all of the cached files/user entries the server will go mad trying to re-cache.
Bottom line is no system administrator will go through all the pain in the *ss to enable and support APC. This is also not a benefit for the company. They would rather have 300 more clients paying them money than dealing with APC and wondering if their server won't go down or something won't go wrong any moment.
A better solution would be if the client gets a (managed) dedicated server.
That way the client will be the only one hosting a site on that server and he could ask the support to install whatever hi wants on the server. This will be a lot more easier and will save the clietn, the sys admin and the hosting company from growing white hair :)
I hope this helps you understand a bit better why APC is not included in shared hostings.