I'll submit a proper bug report in a while, but I noticed that if my kubuntu (the latest LTS version) machine does this.
Steps to reproduce.
Setup:
1. Have a kubuntu 64 bit installation.
2. A connection to a router via LAN cable.

Steps:
1. Turn off the machine and the router.
2. Turn on the machine and wait till booted completely, log in and have the machine idling on the desktop.
3. Turn on the router.

Notice:
The router never connects.

This only happens if the router was plugged in to the computer and turned off. It doesn't happen if it was already on or not connected at all during boot.
Nothing is wrong with the router as I can reproduce the bug at will following those steps. It is with that very router that I am online right now.