Look around for programs that send a "magic packet" (no kidding, that's what they call it).
www.dslreports.com has something on their tools page to send this, for example.
It's any Ethernet frame with a certain sequence at the END that the MAC controller in the NIC interprets specially and signals a wake-up. Obviously, the NIC's PHY and MAC need to be on to do this, and thus the NIC mostly has to be on. Remember though that ATX systems don't like to turn all the way off, the PCI bus remains powered unless you cut off at the power supply or cord.
I'm not sure if I agree with previous comments that the LEDs must be on. If I were designing for maximum power savings, I'd just not power the LEDs on while in almost-but-not-off mode. In any case, this is a NIC dependent issue.
Also, not all NICs support Wake-on-LAN, and not all NICs that support it actually get it right. If you have a $5 NIC, it might not. And I do believe the exact same is true for your BIOS (not all do it, not all get it right), and you probably have to enable it in the BIOS power management configuration.