unable to install locate or mlocate

Question

I have a fresh install of Ubuntu 12.04.3 LTS

Ruinning cat /etc/apt/sources.list

shows:

deb http://archive.ubuntu.com/ubuntu precise main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu precise-updates main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu precise-security main restricted universe multiverse

but if I run sudo apt-get update && sudo apt-get install mlocate locate
I get

Package locate is a virtual package provided by:
  locate:i386 4.4.2-4ubuntu1 [Not candidate version]

E: Package 'mlocate' has no installation candidate
E: Package 'locate' has no installation candidate

Please help! I never realised how much I depend on the find command..

Cheers, Paul

Update to answer @braiam

#apt-cache policy locate mlocate
locate:
  Installed: (none)
  Candidate: (none)
  Package pin: 4.4.2-4ubuntu1
  Version table:
     4.4.2-4ubuntu1 -10
        500 http://archive.ubuntu.com/ubuntu/ precise/universe amd64 Packages
mlocate:
  Installed: (none)
  Candidate: (none)
  Package pin: 0.23.1-1ubuntu2
  Version table:
     0.23.1-1ubuntu2 -10
        500 http://archive.ubuntu.com/ubuntu/ precise/main amd64 Packages




#uname -a
Linux xxxx 3.0.20-xenU #1 SMP Wed May 15 04:27:08 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux

Second update to answer @braiam

:~# dpkg --print-foreign-architectures
i386
:~# cat /var/lib/dpkg/arch
amd64
i386

Third update to answer @braiam

sudo apt-get update
Get:1 http://security.ubuntu.com precise-security Release.gpg [198 B]
Hit http://archive.ubuntu.com precise Release.gpg    
Get:2 http://security.ubuntu.com precise-security Release [49.6 kB]
Get:3 http://archive.ubuntu.com precise-updates Release.gpg [198 B]
Hit http://archive.ubuntu.com precise Release                   
Get:4 http://archive.ubuntu.com precise-updates Release [49.6 kB]               
Get:5 http://security.ubuntu.com precise-security/main amd64 Packages [342 kB]
Hit http://archive.ubuntu.com precise/main amd64 Packages          
Hit http://archive.ubuntu.com precise/restricted amd64 Packages
Hit http://archive.ubuntu.com precise/universe amd64 Packages          
Get:6 http://security.ubuntu.com precise-security/restricted amd64 Packages [4,627 B]
Hit http://archive.ubuntu.com precise/multiverse amd64 Packages        
Get:7 http://security.ubuntu.com precise-security/universe amd64 Packages [85.2 kB]
Hit http://archive.ubuntu.com precise/main i386 Packages               
Get:8 http://security.ubuntu.com precise-security/multiverse amd64 Packages [2,439 B]
Hit http://archive.ubuntu.com precise/restricted i386 Packages         
Get:9 http://security.ubuntu.com precise-security/main i386 Packages [360 kB]
Hit http://archive.ubuntu.com precise/universe i386 Packages
Hit http://archive.ubuntu.com precise/multiverse i386 Packages
Hit http://archive.ubuntu.com precise/main TranslationIndex
Hit http://archive.ubuntu.com precise/multiverse TranslationIndex
Hit http://archive.ubuntu.com precise/restricted TranslationIndex
Hit http://archive.ubuntu.com precise/universe TranslationIndex
Get:10 http://archive.ubuntu.com precise-updates/main amd64 Packages [708 kB]                                                                                                                                                 
Get:11 http://security.ubuntu.com precise-security/restricted i386 Packages [4,620 B]                                                                                                                                         
Get:12 http://security.ubuntu.com precise-security/universe i386 Packages [88.9 kB]                                                                                                                                           
Get:13 http://security.ubuntu.com precise-security/multiverse i386 Packages [2,635 B]                                                                                                                                         
Hit http://security.ubuntu.com precise-security/main TranslationIndex                                                                                                                                                         
Hit http://security.ubuntu.com precise-security/multiverse TranslationIndex                                                                                                                                                   
Hit http://security.ubuntu.com precise-security/restricted TranslationIndex                                                                                                                                                   
Hit http://security.ubuntu.com precise-security/universe TranslationIndex                                                                                                                                                     
Get:14 http://archive.ubuntu.com precise-updates/restricted amd64 Packages [11.5 kB]                                                                                                                                          
Hit http://security.ubuntu.com precise-security/main Translation-en                                                                                                                                                           
Get:15 http://archive.ubuntu.com precise-updates/universe amd64 Packages [222 kB]                                                                                                                                             
Hit http://security.ubuntu.com precise-security/multiverse Translation-en                                                                                                                                                     
Hit http://security.ubuntu.com precise-security/restricted Translation-en                                                                                                                                                     
Hit http://security.ubuntu.com precise-security/universe Translation-en                                                                                                                                                       
Get:16 http://archive.ubuntu.com precise-updates/multiverse amd64 Packages [14.0 kB]                                                                                                                                          
Get:17 http://archive.ubuntu.com precise-updates/main i386 Packages [729 kB]                                                                                                                                                  
Get:18 http://archive.ubuntu.com precise-updates/restricted i386 Packages [11.4 kB]                                                                                                                                           
Get:19 http://archive.ubuntu.com precise-updates/universe i386 Packages [226 kB]                                                                                                                                              
Get:20 http://archive.ubuntu.com precise-updates/multiverse i386 Packages [14.2 kB]                                                                                                                                           
Hit http://archive.ubuntu.com precise-updates/main TranslationIndex                                                                                                                                                           
Hit http://archive.ubuntu.com precise-updates/multiverse TranslationIndex                                                                                                                                                     
Hit http://archive.ubuntu.com precise-updates/restricted TranslationIndex                                                                                                                                                     
Hit http://archive.ubuntu.com precise-updates/universe TranslationIndex                                                                                                                                                       
Hit http://archive.ubuntu.com precise/main Translation-en                                                                                                                                                                     
Hit http://archive.ubuntu.com precise/multiverse Translation-en                                                                                                                                                               
Hit http://archive.ubuntu.com precise/restricted Translation-en                                                                                                                                                               
Hit http://archive.ubuntu.com precise/universe Translation-en                                                                                                                                                                 
Hit http://archive.ubuntu.com precise-updates/main Translation-en                                                                                                                                                             
Hit http://archive.ubuntu.com precise-updates/multiverse Translation-en                                                                                                                                                       
Hit http://archive.ubuntu.com precise-updates/restricted Translation-en                                                                                                                                                       
Hit http://archive.ubuntu.com precise-updates/universe Translation-en                                                                                                                                                         
Fetched 2,925 kB in 19s (150 kB/s)                                                                                                                                                                                            
Reading package lists... Done

Answer 1

Create the /var/lib/dpkg/arch file with the following text:

amd64
i386

Then do, sudo apt-get update and now you can start installing things again.

Answer 2

After further investigation it turns out this has been disabled by the hosting company.

By default mlocate is not installed, and disabled if it is installed by default. The reason for this is due to the cron tasks and IO load it puts on the servers which can impact other servers on the same host. IO is the biggest cause for slow down on hosts which is why we are fairly strict. We prefer to encourage people to use the find command to find things eg find / -iname "somename"

When trying to figure this out the first place I turned to was google, I was unable to find anything useful on this problem.

I have added this as an answer so that hopefully people Googleing "unable to install locate" in the future can know to ask their hosting company first!