What version of metasploit is installed? Can you provide the output of:
dpkg -l | grep metasploit

The Metasploit packages for Kali are updated once per week from Rapid7's stable update tree. If you prefer bleeding edge git updates, you can use git to clone the open source framework from https://github.com/rapid7/metasploit-framework.

Output:

ii metasploit 4.5.3-2013032001-1kali0 i386 Penetration testing and exploit development tool with web-based interface
ii metasploit-framework 4.5.3-2013032001-1kali4 i386 Framework for exploit development and vulnerability research

A new update was just released (https://community.rapid7.com/docs/DOC-2232). Can you try msfupdate now and see if it works?

I tried msfupdate. As usual, the output is:

[]
[] Attempting to update the Metasploit Framework...
[*]

[] Checking for updates
[] No updates available

Thanks for the quick response. Can you run:

apt-get update

and then copy and paste the output of:

apt-cache policy metasploit-framework metasploit

In Kali, msfupdate looks at the difference between the currently installed version and the candidate version.

Output:

metasploit-framework:
Instalado: 4.5.3-2013032001-1kali4
Candidato: 4.5.3-2013032001-1kali4
Tabela de Versão:
4.5.3-2013032001-1kali4 0
500 http://http.kali.org/kali/ kali/main i386 Packages
100 /var/lib/dpkg/status
metasploit:
Instalado: 4.5.3-2013032001-1kali0
Candidato: 4.5.3-2013032001-1kali0
Tabela de Versão:
4.5.3-2013032001-1kali0 0
500 http://http.kali.org/kali/ kali/non-free i386 Packages
100 /var/lib/dpkg/status

Sorry, it's in portuguese

Instalado = Installed
Candidato = Candidate
Tabela de Versão = Version Table

Thank you for your patience and quick feedback. There are two problems:

1) There is an error in the msfupdate code when the system language is not English. This will be fixed in next week's Metasploit update. A temporary workaround would be to run msfupdate in english:
LANG="en_US.UTF-8" msfupdate

2) On your install, apt-get update is not pulling the latest updates from the Kali server. When you run
apt-get update
you should see output similar to:
Hit http://http.kali.org kali/contrib Sources
Hit http://http.kali.org kali/non-free amd64 Packages
...
If you do not see this, ensure that your /etc/apt/sources.list file contains the following:
deb http://http.kali.org/kali kali main contrib non-free
deb-src http://http.kali.org/kali kali main contrib non-free
deb http://security.kali.org/kali-security kali/updates main contrib non-free
deb-src http://security.kali.org/kali-security kali/updates main contrib non-free

No problem, i want to help improving kali!

1) It doesn't seem to work for me!

2) Output of apt-get update:
Hit http://repo.kali.org kali-bleeding-edge InRelease
Hit http://repo.kali.org kali-bleeding-edge/main i386 Packages
Hit http://http.kali.org kali InRelease
Hit http://security.kali.org kali/updates InRelease
Hit http://http.kali.org kali/main Sources
Hit http://security.kali.org kali/updates/main Sources
Hit http://http.kali.org kali/contrib Sources
Hit http://security.kali.org kali/updates/contrib Sources
Hit http://http.kali.org kali/non-free Sources
Hit http://security.kali.org kali/updates/non-free Sources
Hit http://http.kali.org kali/main i386 Packages
Hit http://security.kali.org kali/updates/main i386 Packages
Ign http://repo.kali.org kali-bleeding-edge/main Translation-en_US
Hit http://http.kali.org kali/contrib i386 Packages
Ign http://repo.kali.org kali-bleeding-edge/main Translation-en
Hit http://security.kali.org kali/updates/contrib i386 Packages
Hit http://http.kali.org kali/non-free i386 Packages
Hit http://security.kali.org kali/updates/non-free i386 Packages
Ign http://security.kali.org kali/updates/contrib Translation-en_US
Ign http://security.kali.org kali/updates/contrib Translation-en
Ign http://security.kali.org kali/updates/main Translation-en_US
Ign http://http.kali.org kali/contrib Translation-en_US
Ign http://security.kali.org kali/updates/main Translation-en
Ign http://http.kali.org kali/contrib Translation-en
Ign http://security.kali.org kali/updates/non-free Translation-en_US
Ign http://http.kali.org kali/main Translation-en_US
Ign http://security.kali.org kali/updates/non-free Translation-en
Ign http://http.kali.org kali/main Translation-en
Ign http://http.kali.org kali/non-free Translation-en_US
Ign http://http.kali.org kali/non-free Translation-en
Reading package lists... Done

Seems everything's fine right?

3) nano /etc/apt/sources.list :

deb http://http.kali.org/kali kali main contrib non-free
deb-src http://http.kali.org/kali kali main contrib non-free
deb http://security.kali.org/kali-security kali/updates main contrib non-free
deb-src http://security.kali.org/kali-security kali/updates main contrib non-free
deb http://repo.kali.org/kali kali-bleeding-edge main

Again, everything seems fine, right?

This has been fixed in metasploit-framework 4.5.3-2013040301. Since msfupdate is broken for non-english locales prior to 2013040301, users should use apt to update:

apt-get update
apt-get install metasploit-framework metasploit

Plastico, we still need to understand why your apt cache isn't updating. Hopefully this was a timing issue and it is fixed now?