Just wanted to post my conclusion in case anyone else has a similar problem. I have 2 onboard network controllers and neither was working the first time I booted, the last thing I tried was disabling one of the controllers in the BIOS leaving only 1 working and just plugged my network cable into the single working one. To my amazement, this actually solved my problem and I can now access the internet straight away every time I boot.
Thanks for providing the update. Seems odd for a motherboard to be released with a problem like that.