I want to be able to start XBMC Live remotely. XBMC being based on Ubuntu, it was not so hard to achieve, once I understood I should follow the Ubuntu tutorial rather than the XBMC one.
You may need to install the ethtool package
sudo apt-get install ethtool
You can then try to enable WOL manually
sudo ethtool -s eth0 wol g
You can check the command worked by running
sudo ethtool eth0
Which should give you Supports Wake-on: g
Now, to automate this each time Ubuntu starts, one needs to edit /etc/rc.local
ethtool -s eth0 wol g
Before the line exit 0
Assumed that the BIOS supports WOL and that WOL is enabled, you should be able to start your Ubuntu / XBMC PC remotely.