Hi Elmi,
I've just installed Ubuntu 12.04.5 LTS in a Virtual Machine just to try to reproduce your issue but it is working fine and the python version installed is 2.7.3:
root@ubuntu:~/letsencrypt# lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 12.04.5 LTS
Release: 12.04
Codename: precise
root@ubuntu:~/letsencrypt# python --version
Python 2.7.3
Sorry but I have run out of ideas, maybe you should take a look to other clients like this one that is written in bash and has no python dependencies.
Cheers,
sahsanu