Jeremy Davis's picture

But TKL is build from scratch using an Ubuntu 10.04 based JeOS with Ubuntu 10.04 packages rather than a reduced/improved Ubuntu 10.04 Server install.

locate and mlocate appear to be separate packages, try:

apt-get update && apt-get install locate mlocate