It has nothing to do with the BIOS at all - you misunderstood me.
It is not "Boot from LAN" like you would boot from a HDD or a CDROM, it IS an OS specific issue, because when I was using Fedora Core 3 I fixed it, but I can't for the life of me remember how.
When LINUX is booting and AFTER Grub has passed, it detects my hardware, goes through the standard boot procedure, mounting filesystems etc, but when it gets to "Configuring Network Interfaces" it pauses for 60 seconds when no cable is plugged in.
Additionally because of that, I also get a smaller pause when LINUX tries to contact an NTP time server, because there is no connection to my network.
Like I said before, it works fine when a network cable is plugged in, but it is nothing whatsoever to do with "Boot from LAN" or "Wake on LAN".