in your question you mentioned that your phpinfo was stating that apache was loading xdebug's configuration in /etc/php5/apache2/conf.d/xdebug.ini In many of the instructions online you may note that they ask you to put xdebug config in php.ini (and that is what I did) HOWEVER, if the configuration is set to /etc/php5/apache2/conf.d/xdebug.ini, then you should remove the [XDebug] configuration settings from /etc/php5/apache2/php.ini and put it in /etc/php5/apache2/conf.d/xdebug.ini INSTEAD. Once I removed from /etc/php5/apache2/php.ini and put in /etc/php5/apache2/conf.d/xdebug.ini instead, and restarted apache, it worked!!
Therefore, in your /etc/php5/apache2/conf.d/xdebug.ini, put the following:
[XDebug]
zend_extension="/usr/lib/php5/20121212+lfs/xdebug.so"
xdebug.remote_enable=1
xdebug.remote_port="9000"
xdebug.profiler_enable=1
xdebug.profiler_output_dir="/home/paul/tmp"
xdebug.remote_host="localhost"
xdebug.remote_handler="dbgp";
xdebug.idekey="phpstorm_xdebug"
then remove this from the /etc/php5/apache2/php.ini if you put it there as well.
Then do:
sudo service apache2 restart
Then it should work!!!