Is it a wireless connection? I'd disable the adapter, reboot, and see if it quickens up. If it does, it might be a driver problem so I'd download the most up-to-date driver for your adapter.
It's also worth checking the event viewer to see if it provides any clues. A slow start up could mean a number of things, but if it's a fairly fresh install it should not be taking 3 minutes or more to come to life.