Existe um repositório PPA (Personal Package Archive) com o PHP 5.3.6 no link com instruções de instalação. Como eu verifiquei, também é o amd64 build (lucid).
sudo add-apt-repository ppa:bjori/php5
sudo apt-get update
sudo aptitude show php5
Package: php5
State: not installed
Version: 5.3.6-8ubuntu0ppa4~lucid1
Priority: optional
Section: php
Maintainer: Hannes Magnusson <[email protected]>
..
sudo aptitude install php5 php5-cli
php -v
PHP 5.3.6-8ubuntu0ppa4~lucid1 (cli) (built: May 5 2011 22:11:21)
Copyright (c) 1997-2011 The PHP Group
Zend Engine v2.3.0, Copyright (c) 1998-2011 Zend Technologies
Note que você precisa ativar o repositório do universo para isso.