Ubuntu, E: Unable to locate package

So I am trying to install packages on a newly installed Ubuntu box from aptitude but somehow it failed to locate the package.

# apt-get install gcc
Reading package lists... Done
Building dependency tree      
Reading state information... Done
E: Unable to locate package gcc
# aptitude search gcc
#

I am pretty sure the box could connect to the internet so it is quite weird it failed to locate the package.

In fact the issue is pretty straight forward, the local aptitude database didn't contain the software entries and this require an update of the database.

# apt-get update
Ign http://us.archive.ubuntu.com precise InRelease                                                        
Ign http://us.archive.ubuntu.com precise-updates InRelease                                                
Ign http://us.archive.ubuntu.com precise-backports InRelease
Ign http://security.ubuntu.com precise-security InRelease
Get:1 http://us.archive.ubuntu.com precise Release.gpg [198 B]
Get:2 http://us.archive.ubuntu.com precise-updates Release.gpg [198 B]
Get:3 http://security.ubuntu.com precise-security Release.gpg [198 B]
...
...
Get:87 http://us.archive.ubuntu.com precise-backports/restricted Translation-en [14 B]                                                        
Get:88 http://us.archive.ubuntu.com precise-backports/universe Translation-en [8,555 B]                                                       
Fetched 24.8 MB in 32s (769 kB/s)                                                                                                             
Reading package lists... Done

Now the issue is resolved. :-)

# apt-get install gcc
Reading package lists... Done
Building dependency tree      
Reading state information... Done
The following extra packages will be installed:
  binutils cpp cpp-4.6 gcc-4.6 libc-dev-bin libc6-dev libgomp1 libmpc2 libmpfr4 libquadmath0 linux-libc-dev manpages-dev
Suggested packages:
... 
...