These messages appear while waiting for all interfaces marked as 'auto' in /etc/network/interfaces to come up. On most Ubuntu systems, that's only loopback (127.0.0.1); everything else is done later, via NetworkManager.
This usually happens if you've added something marked as both 'auto' and 'dhcp' in that file, and the DHCP server doesn't immediately respond. You'll see this screen until it does.
It might also happen if the device is "missing," for instance if the PCI card isn't seated properly and isn't recognized, or is defective.
So first, look in /etc/network/interfaces and determine what, aside from lo, is marked as auto (alternatively, use this command to print all the auto interfaces:
ifquery --list --allow auto)
Probably, it'll just be your "wifi PCI card," but maybe it's another leftover device you're not using anymore? A wired Ethernet card with no cable plugged in? Remove the 'auto' from anything you don't want to come up at boot (and have to wait for).
If it is just your wireless card, did you mean to configure it this way instead of using NetworkManager? If not, I'd suggest the latter, especially for a wifi interface. Remove the 'auto' and reboot (or just run
ifdown [interface] or even
ifdown -a), log into the graphical desktop, and use the applet in your panel to set up the connection.
If you don't want to use NM for whatever reason, you probably still don't want to wait for the wireless at boot. In this case you'd remove the 'auto' again, and use the
ifup [interface] command to bring it up later. To still do it automatically at boot (but not wait for it), ideally you would create your own upstart script in /etc/init that runs right after static-network-up. If you don't want to figure out how to do that, you could always just slap that command in /etc/rc.local, however.
[interface], by the way, is probably going to be
wlan0, but you should verify this by looking at the output of
ifconfig -a, when it's working.
On to the actual failure, the next time it happens you're going to have to look at /var/log/syslog to find out exactly why. Since you say it works after you reboot, it's probably not going to be a DHCP server issue. More likely, it's an issue with the device. You might see lines like this:
Aug 13 18:45:44 ubuntu dhclient: Error getting hardware address for "wlan0": No such device
Check to see whether the device even appears in the output of
ifconfig -a. If it does, you can manually retry
ifup [interface] (or just
ifup -a if you never removed the autos) to see if it works without rebooting. If not, start looking at the kernel boot messages (
dmesg | less) for anything relevant. Normally there's something printed when the device is first detected, for example:
[ 25.770930] Intel(R) Wireless WiFi driver for Linux
[ 25.770933] Copyright(c) 2003- 2015 Intel Corporation
[ 25.773887] iwlwifi 0000:03:00.0: can't disable ASPM; OS doesn't have ASPM control
[ 26.110349] iwlwifi 0000:03:00.0: loaded firmware version 126.96.36.199 op_mode iwldvm
Look at your own when it's working to see what it should look like. Then, compare to when it's broken. Are there any errors? Or, is the wireless stuff missing altogether? That, to me, just screams poorly seated or defective card. Make very sure it is fully and firmly in the PCI slot.
If you found other kinds of errors, in syslog or in dmesg, you should probably file a bug. Save everything relevant you found in these logs and output of commands. When you are able to connect, run the command
ubuntu-bug networking to create the bug, then attach whatever you saved.