More than FOUR minutes to boot up my Ubuntu 12.04. What could be the problem?

If you run:

dmesg | less

Look for large gaps on the time on the left, what are the lines around the large gaps in time stating?

Have you also tested your RAM using Grub?

Not checked the ram yet. Will do it later

Here's the gap:
[ 28.971126] cfg80211: Updating information on frequency 2484 MHz for a 20 MHz width channel with regulatory rule:
[ 28.971131] cfg80211: 2474000 KHz - 2494000 KHz @ 20000 KHz), (300 mBi, 2000 mBm)
[ 28.971136] cfg80211: World regulatory domain updated:
[ 28.971139] cfg80211: (start_freq - end_freq @ bandwidth), (max_antenna_gain, max_eirp)
[ 28.971144] cfg80211: (2402000 KHz - 2472000 KHz @ 40000 KHz), (300 mBi, 2000 mBm)
[ 28.971148] cfg80211: (2457000 KHz - 2482000 KHz @ 20000 KHz), (300 mBi, 2000 mBm)
[ 28.971152] cfg80211: (2474000 KHz - 2494000 KHz @ 20000 KHz), (300 mBi, 2000 mBm)
[ 28.971157] cfg80211: (5170000 KHz - 5250000 KHz @ 40000 KHz), (300 mBi, 2000 mBm)
[ 28.971161] cfg80211: (5735000 KHz - 5835000 KHz @ 40000 KHz), (300 mBi, 2000 mBm)
[ 32.876296] init: ufw pre-start process (673) terminated with status 1
[ 271.823913] EXT3-fs (sda5): using internal journal
[ 272.856389] RPC: Registered named UNIX socket transport module.
[ 272.856397] RPC: Registered udp transport module.
[ 272.856400] RPC: Registered tcp transport module.
[ 272.856403] RPC: Registered tcp NFSv4.1 backchannel transport module.
[ 272.930834] FS-Cache: Loaded
[ 273.120082] init: ufw pre-start process (1148) terminated with status 1
[ 273.245387] init: failsafe main process (1329) killed by TERM signal
[ 273.314950] NFS: Registering the id_resolver key type
[ 273.314995] FS-Cache: Netfs 'nfs' registered for caching
[ 273.578327] Installing knfsd (copyright (C) 1996 <email address hidden>).
[ 275.425801] dd: sending ioctl 801c6d02 to a partition!
[ 275.425809] dd: sending ioctl 801c6d02 to a partition!
[ 276.742443] audit_printk_skb: 6 callbacks suppressed

I'd test your RAM as well as boot to liveCD and fsck your partitions

RAM Tested, OK.
Still struggling on how to properly do an fsck.

What is the output of:

sudo fdisk -l

Thanks

The output of sudo fdisk -l is:

Disk /dev/sda: 120.0 GB, 120034123776 bytes
255 heads, 63 sectors/track, 14593 cylinders, total 234441648 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x8c38868e

   Device Boot Start End Blocks Id System
/dev/sda1 * 63 51199154 25599546 7 HPFS/NTFS/exFAT
/dev/sda2 51199216 234436544 91618664+ f W95 Ext'd (LBA)
/dev/sda5 51199218 87971939 18386361 83 Linux
/dev/sda6 87972003 94205159 3116578+ 82 Linux swap / Solaris
/dev/sda7 94205223 234436544 70115661 7 HPFS/NTFS/exFAT

Then in live CD you can run:

sudo fsck /dev/sda5

fsck from util-linux 2.21.1
e2fsck 1.42 (29-Nov-2011)
/dev/sda5: clean, 424196/1150560 files, 3437396/4596590 blocks

More data on boot times:
My last bootup lasted
1m40s to login screen, an then
2m40s to full usability, totalling
4m20s.

These might help
Output of mount:
==============
/dev/sda5 on / type ext3 (rw,errors=remount-ro)
proc on /proc type proc (rw,noexec,nosuid,nodev)
sysfs on /sys type sysfs (rw,noexec,nosuid,nodev)
none on /sys/fs/fuse/connections type fusectl (rw)
none on /sys/kernel/debug type debugfs (rw)
none on /sys/kernel/security type securityfs (rw)
udev on /dev type devtmpfs (rw,mode=0755)
devpts on /dev/pts type devpts (rw,noexec,nosuid,gid=5,mode=0620)
tmpfs on /run type tmpfs (rw,noexec,nosuid,size=10%,mode=0755)
none on /run/lock type tmpfs (rw,noexec,nosuid,nodev,size=5242880)
none on /run/shm type tmpfs (rw,nosuid,nodev)
/dev/sda1 on /media/sda1 type fuseblk (rw,nosuid,nodev,allow_other,default_permissions,blksize=4096)
/dev/sda7 on /media/Datos type fuseblk (rw,nosuid,nodev,allow_other,default_permissions,blksize=4096)
binfmt_misc on /proc/sys/fs/binfmt_misc type binfmt_misc (rw,noexec,nosuid,nodev)
rpc_pipefs on /run/rpc_pipefs type rpc_pipefs (rw)
gvfs-fuse-daemon on /home/luis/.gvfs type fuse.gvfs-fuse-daemon (rw,nosuid,nodev,user=luis)

/etc/fstab
========
# /etc/fstab: static file system information.
#
# Use 'blkid -o value -s UUID' to print the universally unique identifier
# for a device; this may be used with UUID= as a more robust way to name
# devices that works even if disks are added and removed. See fstab(5).
#
# <file system> <mount point> <type> <options> <dump> <pass>
proc /proc proc nodev,noexec,nosuid 0 0
# / was on /dev/sda5 during installation
UUID=c016a54f-5b56-4f36-adcc-a8cb375febe5 / ext3 errors=remount-ro 0 1
/dev/sda6 none swap sw 0 0
/dev/sda1 /media/sda1 ntfs nls=iso8859-1,umask=000 0 0
/dev/sda7 /media/Datos ntfs nls=iso8859-1,umask=000,owner,uid=luis 0 0
#192.168.1.15:/home/rodrigo/Música /mnt/musicas nfs defaults 0 0

UPDATE:

Disabling wlan by hardware switch reduces 50s the boot up!

Now it's 3m30s.

Is it worth a bug report?

I'd say so