Embora eu tenha tentado muito mais coisas, acho que estas etapas usando o PHP 5.3.3 backport de Chris Lea resolveu meu problema:
$ sudo add-apt-repository ppa:chris-lea/php5.3.3
$ sudo apt-get update
$ sudo apt-get upgrade
E a versão agora é
$ php -v
PHP 5.3.3-8ubuntu12~lucid1 with Suhosin-Patch (cli) (built: Jan 26 2011 20:34:21)