This one catches me out every time, so documenting here for posterity.
Firstly, make sure
apcu (PHP 5.5+) is installed by running
php -m | grep apc.
If you do have it installed but you're still getting the error
The class 'APCIterator' could not be found. then you probably need to enable APC on the command line. Make sure the following lines exist in your
apc.enabled = onapc.enable_cli = on