In every situation that I have run into this it is a problem in /etc/network/interfaces
You should not have to remove everything as suggested in an earlier post, but rather inspect for common problems.
In my case it was defining the gateway parameter for additional ethernet IPS. You only need to define the gateway for the primary interface for each card.
What I mean by this is if your file looks like this:
iface eth0 inet static
iface eth0:0 inet static
The 2nd gateway param will cause ubuntu to hang for 60+ secs during boot, you only need to define the gateway for the first eth0 section, you DO need to define the gateway for any additional nic cards, IE eth1, wlan0 etc but NOT for additional IPS assigned to the same nic. Earlier version of Ubuntu did not have any issues with this, but Ubuntu 12.04 does not like it... Be nice if it could simply ignore it.
I'm sure there are other "problems" in this file that can cause this, so you should inspect the file and make sure there are no typos etc.